#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
char s[N];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", s);
    getchar();
    vector<int> cnt(27, 0);
    for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'];
    for (int len = n; len >= 1; --len) {
      vector<int> circ, c_cnt, used(len, 0);
      for (int i = 0; i < len; ++i) {
        if (used[i]) continue;
        used[i] = 1;
        int j = (i + k) % len;
        circ.push_back(1);
        while (!used[j]) {
          used[j] = 1;
          circ.back()++;
          j = (j + k) % len;
        }
      }
      c_cnt = cnt;
      sort(circ.begin(), circ.end());
      sort(c_cnt.begin(), c_cnt.end());
      int ok = 1;
      while (!circ.empty()) {
        if (circ.back() > c_cnt.back()) {
          ok = 0;
          break;
        } else {
          c_cnt.back() -= circ.back();
          circ.pop_back();
          sort(c_cnt.begin(), c_cnt.end());
        }
      }
      if (ok) {
        printf("%d\n", len);
        break;
      }
    }
  }
  return 0;
}
