#include <bits/stdc++.h>
using namespace std;
class Solution {
 public:
  int solve(string& S, int K) {
    int n = S.length();
    vector<int> cnts(128, 0);
    for (auto c : S) {
      ++cnts[c];
    }
    vector<int> A;
    for (auto x : cnts) {
      if (x > 0) {
        A.push_back(x);
      }
    }
    sort(A.begin(), A.end());
    vector<bool> visited(n, false);
    auto ok = [&](int n) {
      fill(visited.begin(), visited.end(), false);
      priority_queue<int> pq;
      for (auto x : A) {
        pq.push(x);
      }
      for (int i = 0; i < n; ++i) {
        if (visited[i]) {
          continue;
        }
        int u = i;
        int len = 0;
        do {
          visited[u] = true;
          ++len;
          u = (u + K) % n;
        } while (u != i);
        if (pq.empty() || pq.top() < len) {
          return false;
        }
        {
          int x = pq.top();
          pq.pop();
          x -= len;
          if (x > 0) {
            pq.push(x);
          }
        }
      }
      return true;
    };
    int res = 1;
    for (int i = n; i > 0; --i) {
      if (ok(i)) {
        res = i;
        break;
      }
    }
    return res;
  }
};
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  Solution sol;
  int t;
  cin >> t;
  while (t-- > 0) {
    int n, K;
    cin >> n >> K;
    string S;
    cin >> S;
    cout << sol.solve(S, K) << '\n';
  }
  return 0;
}
