#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, k, c[26], ans = 0;
    memset(c, 0, sizeof(c));
    cin >> n >> k;
    string s;
    cin >> s;
    for (long long int i = 0; i < n; i++) c[s[i] - 'a']++;
    for (long long int l = 1; l <= k && l <= n; l++)
      if (k % l == 0) {
        for (long long int j = l; j <= n; j += l) {
          long long int p = 0, e = j / l;
          for (long long int i = 0; i < 26; i++) {
            p += c[i] / e;
          }
          if (p >= l) ans = max(ans, j);
        }
      }
    cout << ans << "\n";
  }
}
