#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long fast(long long x, long long n) {
  long long ans = 1;
  for (; n; n >>= 1, x = x * x % mod)
    if (n & 1) ans = ans * x % mod;
  return ans;
}
const int N = 2005;
int n, k, ans;
char s[N];
int num[200];
int main() {
  int cas;
  cin >> cas;
  while (cas--) {
    cin >> n >> k;
    scanf("%s", s + 1);
    memset(num, 0, sizeof num);
    for (int i = 1; i <= n; i++) num[s[i]]++;
    int ans = 0;
    for (int i = 'a'; i <= 'z'; i++) ans = max(ans, num[i]);
    for (int i = 1; i <= k; i++)
      if (k % i == 0) {
        int L = 1, R = n, tempans = 0;
        while (L <= R) {
          int mid = L + R >> 1;
          if (mid * i > n)
            R = mid - 1;
          else {
            int cnt = 0;
            for (int i = 'a'; i <= 'z'; i++) {
              cnt += num[i] / mid;
            }
            if (cnt >= i)
              L = mid + 1, tempans = mid * i;
            else
              R = mid - 1;
          }
        }
        ans = max(ans, tempans);
      }
    cout << ans << endl;
  }
}
