#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9 + 123, MAXN = 2e5 + 47, MEGAINF = 1e18;
template <class T>
inline istream& operator>>(istream& in, vector<T>& a) {
  for (auto& i : a) in >> i;
  return in;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& a) {
  for (auto& i : a) out << i << " ";
  return out;
}
template <class T, class U>
inline istream& operator>>(istream& in, vector<pair<T, U>>& a) {
  for (auto& i : a) in >> i.first >> i.second;
  return in;
}
template <class T, class U>
inline ostream& operator<<(ostream& out, vector<pair<T, U>>& a) {
  for (auto& i : a) out << i.first << " " << i.second << endl;
  return out;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
signed main() {
  setlocale(LC_ALL, "rus");
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<long long> cnt(26);
    for (auto& i : s) ++cnt[i - 'a'];
    long long res = 0;
    for (long long len = 1; len <= n; ++len) {
      long long x = len / gcd(len, k);
      long long grab = 0;
      for (long long u = 0; u < 26; ++u) grab += cnt[u] / x * x;
      if (grab >= len) res = len;
    }
    cout << res << "\n";
  }
}
