#include <bits/stdc++.h>
using namespace std;
vector<long long int> prime, sfac;
vector<long long int> ps;
void sieve(long long int n) {
  prime.assign(n + 1, 1);
  sfac.assign(n + 1, 1);
  for (int p = 2; p * p <= 1e+7; p++) {
    if (prime[p] == 1) {
      sfac[p] = p;
      for (int i = p * p; i <= 1e+7; i += p) {
        prime[i] = 0;
        sfac[i] = p;
      }
    }
  }
  for (auto i = prime.begin(); i != prime.end(); i++) {
    if (*i == 1) ps.push_back(*i);
  }
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
int main() {
  long long int tt;
  cin >> tt;
  while (tt--) {
    long long int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    map<char, int> m;
    for (int i = 0; i < s.size(); i++) m[s[i]]++;
    int ch[27];
    int max = 1;
    for (int cl = 2; cl <= n; cl++) {
      int p[cl];
      int visited[cl];
      int cyc[cl];
      for (int i = 0; i < cl; i++) {
        p[i] = (i + k) % cl;
        visited[i] = 0;
        cyc[i] = 0;
      }
      int x = 0;
      for (int i = 1; i < 27; i++) {
        ch[i] = m[(char)(96 + i)];
      }
      for (int i = 0; i < cl; i++) {
        if (visited[i]) continue;
        int node = i;
        while (1) {
          if (visited[node]) break;
          cyc[x]++;
          visited[node] = 1;
          node = p[node];
        }
        x++;
      }
      int fl1 = 0;
      for (int i = 0; i < x; i++) {
        int count = cyc[i];
        int fl = 0;
        for (int j = 1; j < 27; j++) {
          if (ch[j] < count) continue;
          if (ch[j] >= count) {
            ch[j] -= count;
            fl = 1;
            break;
          }
        }
        if (fl == 0) {
          fl1 = 1;
          break;
        }
      }
      if (!fl1) max = cl;
    }
    cout << max << endl;
  }
}
