#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int par[MAXN];
int sz[MAXN];
int getpar(int x) { return x == par[x] ? x : (par[x] = getpar(par[x])); }
void join(int a, int b) {
  int pa = getpar(a);
  int pb = getpar(b);
  if (pa != pb) {
    par[pa] = par[pb];
  }
}
int t, n, k;
string s;
int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cin >> s;
    int ans = 0;
    for (int len = 1; len <= n; len++) {
      vector<int> cnt(26);
      for (int i = 0; i < n; i++) {
        cnt[s[i] - 'a']++;
      }
      sort(cnt.begin(), cnt.end());
      reverse(cnt.begin(), cnt.end());
      for (int i = 0; i < len; i++) {
        par[i] = i;
        sz[i] = 0;
      }
      for (int i = 0; i < len; i++) {
        join(i, (i + k) % len);
      }
      vector<int> v;
      for (int i = 0; i < len; i++) {
        sz[getpar(i)]++;
      }
      for (int i = 0; i < len; i++) {
        if (sz[i] > 0) {
          v.push_back(sz[i]);
        }
      }
      sort(v.begin(), v.end());
      reverse(v.begin(), v.end());
      bool valid = 1;
      int i = 0;
      for (int j = 0; i < v.size() && j < cnt.size();) {
        if (v[i] <= cnt[j]) {
          cnt[j] -= v[i];
          i++;
        } else {
          j++;
        }
      }
      if (i == v.size()) ans = max(ans, len);
    }
    cout << ans << '\n';
  }
}
