#include <bits/stdc++.h>
using namespace std;
char s[100010];
int t, n, k, cnt[30], ans = 0;
bool check(int sum, int len) {
  for (int i = 0; i <= 25; i++) {
    sum -= cnt[i] / len;
    if (sum <= 0) return true;
  }
  return false;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    ans = 0;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) {
      cnt[s[i] - 'a']++;
      ans = max(ans, cnt[s[i] - 'a']);
    }
    for (int i = 2; i <= k; i++) {
      if (k % i != 0) continue;
      int l = 1, r = n / i;
      while (l <= r) {
        int mid = (l + r) / 2;
        if (check(i, mid))
          ans = max(ans, mid * i), l = mid + 1;
        else
          r = mid - 1;
      }
    }
    printf("%d\n", ans);
  }
}
