#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return (b ? gcd(b, a % b) : a); }
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    map<char, long long> freq;
    for (auto it : s) {
      freq[it]++;
    }
    long long answer = 1;
    for (long long i = 1; i <= n; i++) {
      long long e = gcd(i, k);
      long long rep = i / e;
      long long len = 0;
      for (auto it : freq) {
        len += it.second / rep;
      }
      if (len >= e) {
        answer = max(answer, i);
      }
    }
    cout << answer << '\n';
  }
  return 0;
}
