#include <bits/stdc++.h>
int solve() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> counter(26, 0);
  std::string str;
  std::cin >> str;
  for (char c : str) {
    ++counter[c - 'a'];
  }
  std::sort(counter.begin(), counter.end(), std::greater<int>());
  int res = n;
  if (counter[0] == res) {
    std::cout << res << std::endl;
    return 0;
  }
  while (res > 1) {
    std::vector<bool> used(res, false);
    std::vector<int> cucles;
    for (int cur = 0; cur < res; ++cur) {
      if (used[cur]) {
        continue;
      }
      int i = (cur + k) % res;
      used[cur] = true;
      cucles.push_back(0);
      cucles.back()++;
      while (!used[i]) {
        cucles.back()++;
        used[i] = true;
        i = (i + k) % res;
      }
    }
    std::vector<int> counter_copy(counter);
    std::sort(cucles.begin(), cucles.end(), std::greater<int>());
    bool ok = true;
    while (!cucles.empty()) {
      if (counter_copy[0] < cucles[0]) {
        ok = false;
        break;
      } else {
        counter_copy[0] -= cucles[0];
        cucles.erase(cucles.begin());
        std::sort(counter_copy.begin(), counter_copy.end(),
                  std::greater<int>());
      }
    }
    if (ok) {
      std::cout << res << std::endl;
      return 0;
    }
    --res;
  }
  std::cout << res << std::endl;
  return 0;
}
int main() {
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
