#include <bits/stdc++.h>
using namespace std;
void print(vector<int> &v) {
  for (int i : v) cout << i << " ";
  cout << endl;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> counts(26, 0);
    for (char c : s) counts[c - 'a']++;
    sort(counts.begin(), counts.end());
    for (int length = n; length >= 1; length--) {
      vector<int> cycle_lens;
      vector<int> visited(length, 0);
      for (int i = 0; i < length; i++) {
        if (visited[i]) continue;
        visited[i] = 1;
        cycle_lens.push_back(0);
        cycle_lens.back()++;
        int j = (i + k) % length;
        while (!visited[j]) {
          cycle_lens.back()++;
          visited[j] = 1;
          j = (j + k) % length;
        }
      }
      sort(cycle_lens.begin(), cycle_lens.end());
      vector<int> cts;
      for (int i : counts) cts.push_back(i);
      bool possible = true;
      while (!cycle_lens.empty()) {
        while (!cts.empty() && cts.back() < cycle_lens.back()) cts.pop_back();
        if (cts.empty()) {
          possible = false;
          break;
        }
        cts.back() -= cycle_lens.back();
        cycle_lens.pop_back();
      }
      if (!possible) continue;
      cout << length << endl;
      break;
    }
  }
}
