/* Author : fenwick123 */

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        int n ;
        long long k;
        cin >> n >> k;
        string s;
        cin >> s;
        map<char, long long> cnt;
        for (auto x  : s){
            cnt[x]++;
        }
        long long ans = 0;
        vector<long long> fact;
        for (long long i = 1; i * i <= k ; i++){
            if (k % i == 0){
                fact.push_back (i);
                if (i * i != k){
                    fact.push_back (k / i);
                }
            }
        }
        sort (fact.begin () , fact.end());
        multiset<long long> ms;
        for (auto x : cnt){
            ms.insert (x.second);
        }

        auto works = [&] (int x , int y){
            long long av = 0;
            for (auto it = ms.rbegin(); it != ms.rend(); it++){
              av += (*it / x);
            }
            return av >= y;
        };
        for (int i = 0; i < (int) fact.size(); i++){
            long long size = fact[i];
            long long lo = 1 , hi = n;
            long long x = -1;
            while (lo <= hi){
                long long mid = (lo + hi) / 2;
                if (works (mid , size)){
                    x = mid;
                    lo = mid + 1;
                } else hi = mid - 1;
            }
            ans = max (ans , x * size);
        }
        cout <<  ans << endl;
    }
}