t = int(input())
for i in range(t):
n , k = map(int , input().split())
s = input()
dic ={}
for j in range(len(s)):
if s[j] in dic:
dic[s[j]] += 1
else:
dic[s[j]] = 1
pairs = 0
singles= 0
for i in dic.values():
pairs += i//2
singles += i%2
ll = pairs//k
singles+= (pairs%k)*2
ll = ll*2
if singles>=k:
ll+=1
print(ll)// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define init ios::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define lowbits(x) (x&(-x))
#define INF 0x3f3f3f3f
#define uu __int128
#define PI acos(-1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PII;
const int N=2e5+10, M=2*N;
const int mod=998244353;
const double eps=1e-6;
int n,k;
string s;
int cnt[26];
int dist[N];
void solve(){
cin >> n >> k;
cin >> s;
memset(cnt, 0, sizeof cnt);
for(int i=0; i<n; ++i){
cnt[s[i]-'a']++;
}
int ji=0,d=0;
for(int i=0; i<26; ++i){
if(cnt[i] & 1)++ji;
d += cnt[i]/2;
}
int ans=d/k * 2;
ji += d%k * 2;
if(ji >= k){
++ans;
}
cout << ans << endl;
}
int main()
{
init;
int t=1;
cin >> t;
while(t--)solve();
return 0;
}
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |
Zoos | Build a graph |
Almost correct bracket sequence | Count of integers |
Differences of the permutations | Doctor's Secret |
Back to School | I am Easy |
Teddy and Tweety | Partitioning binary strings |
Special sets | Smallest chosen word |
Going to office | Color the boxes |
Missing numbers | Maximum sum |
13 Reasons Why | Friend's Relationship |
Health of a person | Divisibility |
A. Movement | Numbers in a matrix |
Sequences | Split houses |