#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
const long long mod = 1e9 + 7;
char s[maxn];
int buc[30];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    scanf("%s", s + 1);
    for (int i = (0); i <= (25); i++) buc[i] = 0;
    for (int i = (1); i <= (n); i++) buc[s[i] - 'a']++;
    int mx = 0;
    for (int i = (0); i <= (25); i++) mx = max(mx, buc[i]);
    int ans = mx;
    for (int i = (mx); i <= (n); i++) {
      for (int j = (1); j <= (i); j++) {
        if (i % j || k % j) continue;
        int cnt = 0;
        for (int p = (0); p <= (25); p++) cnt += buc[p] / (i / j);
        if (cnt >= j) ans = i;
      }
    }
    printf("%d", ans);
    puts("");
  }
}
