#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long modi) {
  long long res = 1;
  while (b) {
    if (b % 2) {
      res = (res * a) % modi;
    }
    b /= 2;
    a = (a * a) % modi;
  }
  return res;
}
long long dirx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
long long diry[] = {-1, 0, 1, -1, 1, -1, 0, 1};
long long dx[] = {-1, 1, 0, 0};
long long dy[] = {0, 0, -1, 1};
long long n, m, k;
long long cur, sum, res, ans, x, y, z;
long long a[1000005], b[1000005], c[1000005];
vector<long long> vt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int arr[30] = {0};
    for (int i = 0; i < n; i++) arr[s[i] - 'a']++;
    int mx = 0;
    for (int i = 0; i < 26; i++) mx = max(mx, arr[i]);
    int ans = mx;
    for (int i = 1; i <= k; i++) {
      if (k % i == 0 && i <= n) ans = max(ans, i);
    }
    for (int i = k; i <= n; i += k) {
      int num = i / k;
      int cnt = 0;
      for (int i = 0; i < 26; i++) cnt += (arr[i] / num);
      if (cnt >= k) {
        ans = max(ans, i);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= i; j++) {
        if (k % j != 0 || i % j != 0) continue;
        int num = i / j;
        int cnt = 0;
        for (int i = 0; i < 26; i++) cnt += (arr[i] / num);
        if (cnt >= j) {
          ans = max(ans, i);
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
