#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  auto calc = [](int x, const vector<int>& cnt) {
    int lo = 1, hi = 2020;
    while (hi - lo > 1) {
      int mid = (lo + hi) >> 1;
      int len = 0;
      for (auto& i : cnt) len += i / mid;
      if (len < x)
        hi = mid;
      else
        lo = mid;
    }
    return lo * x;
  };
  auto solve = [&]() {
    int n, k;
    cin >> n >> k;
    vector<int> cnt(26);
    for (int i = 0; i < n; i++) {
      char ch;
      cin >> ch;
      cnt[ch - 'a']++;
    }
    int ans = 0;
    for (int i = 1; i * i <= k; i++) {
      if (k % i != 0) continue;
      if (i <= n) ans = max(ans, calc(i, cnt));
      if (k / i <= n) ans = max(ans, calc(k / i, cnt));
    }
    return ans;
  };
  int t;
  cin >> t;
  while (t--) cout << solve() << '\n';
  return 0;
}
