#include <bits/stdc++.h>
using namespace std;
const long long maxm = 2e6 + 5;
char s[maxm];
long long f[maxm];
long long a[maxm];
long long b[maxm];
long long n, k;
map<long long, long long> mark;
long long check(long long x, long long mid) {
  long long cnt = 0;
  for (auto i : mark) {
    cnt += i.second / mid;
  }
  return cnt >= x;
}
void solve() {
  cin >> n >> k;
  scanf("%s", s + 1);
  mark.clear();
  for (long long i = 1; i <= n; i++) {
    mark[(long long)s[i]]++;
  }
  long long res = 0;
  for (long long i = 1; i <= k && i <= n; i++) {
    if (k % i) continue;
    long long l = 1, r = n / i;
    long long ans = 0;
    while (l <= r) {
      long long mid = (l + r) / 2;
      if (check(i, mid))
        ans = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    if (ans != -1) {
      res = max(res, ans * i);
    }
  }
  cout << res << endl;
}
signed main() {
  long long T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
