#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  int t;
  cin >> t;
  for (int test = 0; test < t; ++test) {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> cnt(26);
    for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'];
    sort(cnt.rbegin(), cnt.rend());
    int ans = -1;
    for (int m = n; m > 0 && ans < 0; --m) {
      vector<bool> vis(m, false);
      vector<int> comps;
      int sz = 0;
      for (int i = 0; i < m; ++i) {
        if (!vis[i]) {
          for (int j = i; !vis[j]; (j += k) %= m) {
            vis[j] = true;
            ++sz;
          }
          comps.push_back(sz);
          sz = 0;
        }
      }
      sort(comps.rbegin(), comps.rend());
      int p1 = 0;
      int p2 = 0;
      vector<int> tmp(cnt.begin(), cnt.end());
      while (p2 < int(comps.size()) && p1 < 26) {
        if (cnt[p1] >= comps[p2]) {
          ++p2;
          cnt[p1] -= comps[p2];
        } else
          ++p1;
      }
      swap(tmp, cnt);
      if (p2 == int(comps.size())) {
        ans = m;
        break;
      }
    }
    cout << ans << endl;
  }
  cout.flush();
  getchar();
  return 0;
}
