#include <bits/stdc++.h>
using namespace std;
int movei[] = {0, 0, 1, -1, 1, 1, -1, -1};
int movej[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int MXN = 1e5 + 7;
int can(vector<int> &FRQ, int k) {
  int mx = 1;
  while (true) {
    bool makable = true;
    int total = 0;
    for (int x : FRQ) total += x / mx;
    if (total < k) makable = false;
    if (!makable) {
      mx--;
      break;
    }
    mx++;
  }
  return k * mx;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> frq(26, 0);
    for (char c : s) frq[c - 'a']++;
    int ans = 1;
    for (int i = 1; i * i <= k; i++) {
      if (k % i == 0) ans = max({ans, can(frq, i), can(frq, k / i)});
    }
    cout << ans << '\n';
  }
}
