#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x * f;
}
bool cmp(int x, int y) { return x > y; }
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
  int t;
  t = read();
  while (t--) {
    int n = read(), k = read();
    char s[2010];
    scanf("%s", s);
    int m[30];
    memset(m, 0, sizeof(m));
    for (int i = 0; i < n; i++) {
      m[s[i] - 'a']++;
    }
    int ln;
    sort(m, m + 26, cmp);
    for (int i = 0; i < 30; i++) {
      if (m[i] == 0) {
        ln = i;
        break;
      }
    }
    int ans = 0;
    for (int i = n; i >= 1; i--) {
      int c = gcd(i, k);
      int cnt = i / c;
      for (int j = 0; j < ln; j++) {
        c -= m[j] / cnt;
      }
      if (c <= 0) {
        ans = i;
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
