#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
string str;
int mp[28];
vector<int> vv, divisor;
bool check(int x, int d) {
  int tot = 0, i, j;
  for (i = 0; i < vv.size(); i++) {
    tot += (vv[i] / x);
  }
  return (tot >= d);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int line, n, k, i, j;
  cin >> line;
  while (line--) {
    cin >> n >> k >> str;
    memset(mp, 0, sizeof mp);
    vv.clear();
    divisor.clear();
    for (i = 0; i < n; i++) {
      mp[str[i] - 'a']++;
    }
    for (i = 0; i < 26; i++) {
      if (mp[i]) vv.push_back(mp[i]);
    }
    sort(vv.rbegin(), vv.rend());
    for (i = 1; i * i <= k; i++) {
      if (k % i == 0) {
        int div1 = i, div2 = k / i;
        if (div1 == div2) {
          divisor.push_back(div1);
        } else {
          divisor.push_back(div1);
          divisor.push_back(div2);
        }
      }
    }
    int ans = 0;
    for (i = 0; i < divisor.size(); i++) {
      int d = divisor[i];
      int lo = 1, hi = n, mid, indx = -1;
      while (lo <= hi) {
        mid = (lo + hi) / 2;
        bool p = check(mid, d);
        if (p) {
          indx = mid;
          lo = mid + 1;
        } else {
          hi = mid - 1;
        }
      }
      if (indx != -1) {
        ans = max(ans, indx * d);
      }
    }
    cout << ans << endl;
  }
  return 0;
}
