#include <bits/stdc++.h>
using namespace std;
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> gfreq;
    for (auto it : s) {
      gfreq[it]++;
    }
    long long res = 1;
    auto get = [&](long long i) {
      map<char, long long> freq = gfreq;
      set<pair<long long, char>, greater<pair<long long, char>>> order;
      for (auto it : freq) {
        order.insert({it.second, it.first});
      }
      string t = "";
      map<char, long long> new_freq;
      while ((long long)t.length() < i) {
        auto it = *order.begin();
        order.erase(order.begin());
        t += it.second;
        new_freq[it.second]++;
        freq[it.second]--;
        if (freq[it.second]) {
          order.insert(
              {gfreq[it.second] / (new_freq[it.second] + 1), it.second});
        }
      }
      assert((long long)t.length() == i);
      long long times = numeric_limits<long long>::max();
      for (auto it : new_freq) {
        times = min(times, gfreq[it.first] / it.second);
      }
      return i * times;
    };
    for (long long i = 1; i <= min(n, k); i++) {
      if (k % i == 0) {
        res = max(res, get(i));
      }
    }
    cout << res << '\n';
  }
  return 0;
}
