#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const long long inf = 1000000000000000000;
const long long KOK = 100000;
const long long LOG = 30;
const long long li = 500005;
const long long mod = 1000000007;
int n, m, b[li], a[li], k, flag, t;
int cev;
string s;
vector<int> v;
int main(void) {
  cin >> t;
  while (t--) {
    cin >> n >> k >> s;
    map<char, int> mpp;
    int mx = 0;
    for (int i = 0; i < n; i++) mpp[s[i]]++;
    for (int jj = 1; jj * jj <= k; jj++) {
      if (k % jj != 0) continue;
      int bol = jj;
      int bas = 0;
      int son = 4000;
      while (bas <= son) {
        cev = 0;
        for (int i = 0; i < 26; i++) {
          for (int j = n; j >= 0; j--) {
            if (j * ((bas + son) / 2) / bol <= mpp[i + 'a']) {
              cev += j;
              break;
            }
          }
        }
        if (cev >= bol)
          bas = ((bas + son) / 2) + 1;
        else
          son = ((bas + son) / 2) - 1;
      }
      son -= son % bol;
      mx = max(mx, son);
      bol = k / jj;
      bas = 0;
      son = 4000;
      while (bas <= son) {
        cev = 0;
        for (int i = 0; i < 26; i++) {
          for (int j = n; j >= 0; j--) {
            if (j * ((bas + son) / 2) / bol <= mpp[i + 'a']) {
              cev += j;
              break;
            }
          }
        }
        if (cev >= bol)
          bas = ((bas + son) / 2) + 1;
        else
          son = ((bas + son) / 2) - 1;
      }
      son -= son % bol;
      mx = max(mx, son);
    }
    cout << mx << endl;
  }
  return 0;
}
