#include <bits/stdc++.h>
using namespace std;
vector<int> factor;
unordered_map<char, int> mp;
void factor_(int n, int N) {
  vector<int> temp;
  for (int i = 1; i <= (int)sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        temp.push_back(i);
      else {
        temp.push_back(i);
        temp.push_back(n / i);
      }
    }
  }
  for (int i = 0; i < temp.size(); i++)
    if (temp[i] != 1) factor.push_back(temp[i]);
}
bool check(int n, int k) {
  int sum = 0;
  for (auto it = mp.begin(); it != mp.end(); it++) sum += (it->second) / n;
  if (sum >= k)
    return true;
  else
    return false;
}
void solve() {
  factor.clear();
  mp.clear();
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  if (k % n == 0) {
    cout << n << endl;
    return;
  }
  for (int i = 0; i < n; i++) mp[s[i]]++;
  if (n == 1) {
    cout << 1 << endl;
    return;
  }
  int m1 = 0;
  for (auto it = mp.begin(); it != mp.end(); it++) m1 = max(m1, it->second);
  if (k == 1) {
    cout << m1 << endl;
    return;
  }
  int ans = 0;
  factor_(k, n);
  for (int i = 0; i < factor.size(); i++) {
    if (factor[i] <= n) {
      ans = max(ans, factor[i]);
      int j = n / factor[i];
      while (!check(j, factor[i]) && j > 0) j--;
      if (j * factor[i] != 2) ans = max(ans, j * factor[i]);
    }
  }
  ans = max(ans, m1);
  cout << ans << endl;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
