#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 2005;
long long int cnt[26];
long long int n, k;
bool ok(long long int l, long long int k) {
  long long int k2 = k % l;
  if (k2 == 0) return 1;
  if (l % k2 != 0) return cnt[25] >= l;
  long long int need = l / k2;
  for (long long int i = 25; i >= 0; i--) {
    l -= (cnt[i] / need) * need;
    if (l <= 0) return 1;
  }
  return 0;
}
int32_t main() {
  long long int t;
  cin >> t;
  while (t--) {
    for (long long int i = 0; i < 26; i++) cnt[i] = 0;
    string s;
    cin >> n >> k >> s;
    for (long long int i = 0; i < n; i++) cnt[s[i] - 'a']++;
    sort(cnt, cnt + 26);
    long long int ans;
    long long int flag = 1;
    for (ans = n; ans >= 1; ans--) {
      for (long long int i = 1; i * i <= k and flag; i++) {
        if (k % i) continue;
        if (ok(ans, i)) flag = 0;
        if (flag and k / i != i and ok(ans, k / i)) flag = 0;
      }
      if (flag == 0) break;
    }
    cout << ans << "\n";
  }
}
