#include <bits/stdc++.h>
using namespace std;
int main() {
  ios ::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;
    map<char, long long> cnt;
    for (auto x : s) {
      cnt[x]++;
    }
    long long ans = 0;
    vector<long long> fact;
    for (long long i = 1; i * i <= k; i++) {
      if (k % i == 0) {
        fact.push_back(i);
        if (i * i != k) {
          fact.push_back(k / i);
        }
      }
    }
    sort(fact.begin(), fact.end());
    multiset<long long> ms;
    for (auto x : cnt) {
      ms.insert(x.second);
    }
    auto works = [&](int x, int y) {
      long long av = 0;
      for (auto it = ms.rbegin(); it != ms.rend(); it++) {
        av += (*it / x);
      }
      return av >= y;
    };
    for (int i = 0; i < (int)fact.size(); i++) {
      long long size = fact[i];
      long long lo = 1, hi = n;
      long long x = -1;
      while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (works(mid, size)) {
          x = mid;
          lo = mid + 1;
        } else
          hi = mid - 1;
      }
      ans = max(ans, x * size);
    }
    cout << ans << endl;
  }
}
