#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 1;
const int inf = 0x3f3f3f3f;
const double Pi = acos(-1.0);
const long long INF = 0x3f3f3f3f3f3f3f3f;
template <class T, class F>
inline void mem(T a, F b, int c) {
  for (int i = 0; i <= c; ++i) a[i] = b;
}
template <class T>
inline void read(T &x, T xk = 10) {
  char ch = getchar();
  T f = 1, t = 0.1;
  for (x = 0; ch > '9' || ch < '0'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch <= '9' && ch >= '0'; ch = getchar()) x = x * xk + ch - '0';
  if (ch == '.')
    for (ch = getchar(); ch <= '9' && ch >= '0'; ch = getchar(), t *= 0.1)
      x += t * (ch - '0');
  x *= f;
}
int a[30];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    memset(a, 0, sizeof(a));
    int n, k;
    scanf("%d%d", &n, &k);
    string s;
    cin >> s;
    int tot = 0;
    for (int i = 0; i < s.size(); ++i) {
      a[s[i] - 'a']++;
      tot = max(a[s[i] - 'a'], tot);
    }
    int res = 0;
    for (int i = 1; i <= tot; ++i) {
      int t = 0;
      for (int j = 0; j <= 25; ++j) {
        t += a[j] / i;
      }
      for (; t > 0; --t) {
        if (k % t == 0) break;
      }
      res = max(res, i * t);
    }
    printf("%d\n", res);
  }
  return 0;
}
