#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int ans = 0;
  vector<int> all(26);
  for (auto c : s) {
    all[c - 'a']++;
  }
  for (int i = 1; i <= n; i++) {
    int sum = 0;
    int k1 = k % i;
    if (k1 == 0) {
      ans = i;
      continue;
    }
    int f = gcd(i, k);
    int ned = i * k / f / k;
    if (i % ned > 0) continue;
    int g = i / ned;
    for (int y = 0; y < 26; y++) {
      g -= all[y] / ned;
    }
    if (g <= 0) ans = i;
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t > 0) {
    t--;
    solve();
  }
}
