#include <bits/stdc++.h>
using namespace std;
int n, k;
char s[2000005];
int mp[26];
int ans;
bool check(int x) {
  int t = x / k;
  int cnt = 0, tot = 0;
  for (int i = 0; i < 26; i++) {
    if (t) {
      cnt += mp[i] / t;
    }
    tot += mp[i];
  }
  if (t == 0) {
    return tot >= x;
  }
  if (cnt >= k)
    return true;
  else
    return false;
}
void solve() {
  memset(mp, 0, sizeof(mp));
  scanf("%d %d", &n, &k);
  scanf("%s", s);
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    mp[s[i] - 'a']++;
  }
  int ans = 0;
  for (int i = 1; i * i <= k; i++) {
    if (k % i == 0) {
      int t = k;
      k = i;
      int cnt;
      for (cnt = n / k * k; cnt >= 1; cnt -= k) {
        if (check(cnt)) break;
      }
      ans = max(ans, cnt);
      k = t / i;
      for (cnt = n / k * k; cnt >= 1; cnt -= k) {
        if (check(cnt)) break;
      }
      ans = max(ans, cnt);
      k = t;
    }
  }
  printf("%d\n", ans);
}
int main() {
  int T = 1;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}
