#include <bits/stdc++.h>
using namespace std;
int n;
bool can(int m, int k, int counts[]) {
  int totalChars = 0;
  for (int i = 0; i < 26; i++) {
    totalChars += counts[i] / m;
  }
  return totalChars >= k;
}
int findBest(int k, int counts[]) {
  int l = 0, r = n / k;
  while (l < r) {
    int m = (l + r + 1) / 2;
    if (can(m, k, counts)) {
      l = m;
    } else {
      r = m - 1;
    }
  }
  return l * k;
}
void solve() {
  int k;
  cin >> n >> k;
  string s;
  cin >> s;
  int counts[26] = {0};
  for (int i = 0; i < n; i++) {
    counts[s[i] - 'a']++;
  }
  sort(counts, counts + 26, greater<int>());
  int bestLen = 0;
  for (int i = 1; i <= k; i++) {
    if (k % i == 0) {
      bestLen = max(bestLen, findBest(i, counts));
    }
  }
  cout << bestLen << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
