#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 ans = 0;
    for (long long len = n; len >= 1; --len) {
      long long length = gcd(len, k);
      long long count = len / length;
      long long sum = 0;
      for (long long i = 0; i < 26; ++i) sum += cnt[i] / count * count;
      if (sum >= len) {
        ans = len;
        break;
      }
    }
    cout << ans << "\n";
  }
}
