#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long inf = 1e9 + 7;
long long modexp(long long base, long long power) {
  if (power == 0) return 1;
  if (power & 1) return base * modexp(base, power - 1) % inf;
  return modexp(base * base % inf, power / 2);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<long long> cha(26, 0);
    for (long long i = 0; i < n; i++) cha[s[i] - 'a']++;
    vector<long long> fact;
    long long ans = -1;
    for (long long i = 1; i * i <= k; i++) {
      if (k % i == 0) {
        fact.push_back(i);
        fact.push_back(k / i);
      }
    }
    sort(cha.rbegin(), cha.rend());
    for (long long i = 0; i < fact.size(); i++) {
      long long x = fact[i];
      long long p = 1;
      while (x * p <= n) {
        long long sum = 0;
        for (long long i = 0; i < 26; i++) {
          sum += (cha[i] / p);
        }
        if (sum >= x) ans = max(ans, x * p);
        p++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
