暴力就能答对的题，简单喵！

这个故事是酱紫的

有一个长长的队伍，里面住着好多数字小猫，每个小猫都有自己的颜色（就是数组里的数字）。

主人想把它们排成一个方阵，方阵的每一排有固定的人数，叫 m（列数）。排的顺序是：先排第一排，从左到右，再排第二排……一排一排排下去。

主人想要某一整列的小猫全都变成同一个颜色 k。

咱可以：

  • 给某个小猫换颜色（每次改一个数字，花 1 次操作）
  • 改变每一排的猫数（增加或减少列数，每次改 1 个，花 1 次操作）

问：最少需要多少次操作？

咱来一步步说喵！

① 读入数据

  • n：队伍里一共有多少小猫。
  • m：现在每排站几个猫（初始的列数）。
  • k：想要他们变成的颜色。
  • num 数组：每个小猫现在的颜色。

② 尝试“增加每排猫数”

咱们先看看，如果让每排站更多的猫（列数变大），会不会更省事。

从现在的 m 开始，一直试到最多 n（因为每排人数不能超过队伍总人数，否则一排就站完啦）。

对于每一种“每排猫数” i，总代价是：

  • 换衣服次数 = num_cost(i)（详见以下喵）
  • 换排数次数 = i - m（因为从 m 增加到 i，需要 i-m 次操作）

总代价 = 换衣服次数 + 换排数次数。

然后咱用 ans 记录最小的总代价。

但是，这里有一个聪明的小窍门（剪枝）：

如果光是增加排数这一步 i - m 已经比当前找到的最优答案 ans 还要大了，那继续增加排数只会让这一步更大，肯定得不到更小的答案，所以咱就提前结束循环啦。

这就是 i - m < ans 的作用喵。

③ 尝试“减少每排猫数”

类似地，从 m-1 往下试，直到每排最少 1 个猫。

总代价 = num_cost(i) + (m - i)。

剪枝条件 m - i < ans 也一样：如果减少排数这一步已经比当前答案大了，就不用再试更小的 i 了。

num_cost(new_m) —— 看看每排站多少猫时最省事

咱来解释喵！

这个函数就是帮咱算出：如果每排站 new_m 个小猫，那至少要给几个小猫换衣服，才能让某一整列全都变成目标颜色 k。

咱要检查每一列：

  • 第 0 列：下标是 0, new_m, 2*new_m, …（也就是第一排第一个、第二排第一个……）
  • 第 1 列：下标是 1, 1+new_m, 1+2*new_m, …
  • 一直到第 new_m-1 列。

对每一列，数一数有多少个小猫不是颜色 k，那就是这一列需要换的猫数喵。

然后咱从所有列里挑一个最小的，这就是在 new_m 列下最少要换的猫数啦。

举个例子喵！

队伍颜色：1 2 3 1 2 3，目标 k=2，每排站 3 个人。

第 0 列（下标 0,3）：1 1 → 需要换 2 个

第 1 列（下标 1,4）：2 2 → 需要换 0 个

第 2 列（下标 2,5）：3 3 → 需要换 2 个

所以最少需要换 0 个，函数就返回 0 喵。

主人奇怪的需求就美美完成啦喵！

看代码喵！

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

vector<ll> num(2e5);
ll n,m,k;

ll num_cost(ll new_m)
{
    ll now_ans=1e9;
    for(ll i=0;i<new_m;i++)// 看第 i 列
    {
        ll one=0;// 这一列要换颜色的小朋友数量
        for(ll j=i;j<n;j+=new_m)
        {
            if(num[j]!=k) one++;// 如果颜色不是 k，就得换
        }
        now_ans=min(now_ans,one);// 记录这一列需要换的最少人数
    }
    return now_ans;
}

void solve()
{
    ll ans=1e9;
    cin >> n >> m >> k;
    for(ll i=0;i<n;i++) cin >> num[i];

    // 尝试增加每排人数（从 m 往上加）
    for(ll i=m;i<=n&&i-m<ans;i++)
    {
        ans=min(ans,num_cost(i)+i-m);
    }
    // 尝试减少每排人数（从 m 往下减）
    for(ll i=m-1;i>0&&m-i<ans;i--)
    {
        ans=min(ans,num_cost(i)+m-i);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;cin >> T;
    while (T--) solve();
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/