#include <bits/stdc++.h>
#pragma GCC optimize("O2", "unroll-loops", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define int ll
#define ld long double
#define eps 1e-12
#define MOD ((int)1e9+7)
int sqr(int x) {
int l(0), r(x);
int a(x), b((x + 1) >> 1);
while (a > b)
a = b, b = (b + x / b) >> 1;
return a;
}
namespace nCr
{
int fastpo(int base, int exp) {
int ans = 1;
while(exp)
{
if(exp&1) ans = (1ll * ans * base) % MOD;
base = (1ll * base * base) % MOD;
exp >>= 1;
}
return ans;
}
vector<int> fac, inv, finv;
void sz(int n) {
fac.resize(n+3),inv.resize(n+3),finv.resize(n+3);
fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1;
for(int i(1); i<=n; ++i) fac[i]=fac[i-1]*i%MOD;
for(int i(2); i<=n; ++i) inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;
for(int i(2); i<=n; ++i) finv[i]=finv[i-1]*inv[i]%MOD;
}
int C(int n, int r) {
if(n<0 or r>n) return 0;
return(fac[n]*finv[r]%MOD*finv[n-r]%MOD);
}
}
const int C = (1ll << 30) % MOD;
struct FenwickTree {
int size;
vector<int> tree;
FenwickTree(int n) : size(n), tree(n+1) {}
void add(int idx, int delta){
while (idx <= size){
tree[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) const{
int res(0), i(idx);
while (i > 0)
res += tree[i], i -= i & -i;
return res;
}
void reset(){
fill(tree.begin(), tree.end(), 0);
}
};
void GETAC() {
int n, k, c(0), m, q, r, x, f, ans(0);
int A, B, M, R, C;
cin >> R >> C >> k;
vector<vector<pair<int, int>>> vp;
int mxown(0);
vector<vector<int>> grid(R, vector<int>(C));
for(int i(0); i < R; ++i){
for(int j(0); j < C; ++j){
cin >> grid[i][j];
if(grid[i][j] > mxown)
mxown = grid[i][j];
}
}
vp.assign(mxown+1, vector<pair<int, int>>());
for(int i(0); i < R; ++i){
for(int j(0), idx; j < C; ++j){
idx = grid[i][j],
vp[idx].emplace_back(make_pair(i+1, j+1));
}
}
vector<vector<pair<int, int>>> p(mxown);
for (int o(1); o <= mxown; ++o){
if (vp[o].size() > 1){
sort(vp[o].begin(), vp[o].end(), [&](const pair<int,int> &a, const pair<int,int> &b) -> bool{
if(a.first ^ b.first) return a.first < b.first;
else return a.second < b.second;
});
p.emplace_back(vp[o]);
}
}
int l(0), h(max(R, C));
while (l < h){
m = (l + ((h-l) >> 1));
int s(0);
for (int i(1), ai; i <= R; ++i){
ai = min(R, i+m) - max(1ll, i-m) + 1;
s += ai;
}
int sb(0);
for(int j(1), bj; j <= C; ++j){
bj = min(C, j + m) - max(1ll, j-m) + 1;
sb += bj;
}
int pot(s*sb - R*C), same(0);
FenwickTree ft(C);
for(auto &cell : p){
int n(cell.size()), l(0), r(0);
ft.reset();
for(int i(0); i < n; ++i){
int curx(cell[i].first), cury(cell[i].second);
while (r < n and cell[r].first <= curx+m)
ft.add(cell[r].second, 1), ++r;
while (l < n and cell[l].first < curx-m)
ft.add(cell[l].second, -1), ++l;
int cl(max(1ll, (int)(cury-m))), cr(min((int)C, (int)(cury+m))),
f(ft.query(cr) - ft.query(cl-1));
same += f-1;
}
}
(pot >= k+same)? h=m : (l=m+1, ans = l);
}
cout << ans;
}
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
if (!stack) {
exit(1);
}
send = stack + stsize - 16;
send = (char *)((uintptr_t)send & -16L);
asm volatile(
"mov %%rsp, (%0)\n"
"mov %0, %%rsp\n"
:
: "r"(send)
: "memory"
);
func();
asm volatile(
"mov (%0), %%rsp\n"
:
: "r"(send)
: "memory"
);
free(stack);
}
signed main() {
fastio
freopen("D:\\META\\bunny_hopscotch_input.txt", "r", stdin);
freopen("D:\\META\\OUT1.txt", "w", stdout);
int T;
cin >> T;
for (int tc(1); tc <= T; ++tc){
cout << "Case #" << tc << ": ";
run_with_stack_size(GETAC, 1024 * 1024 * 1024);
cout << "\n";
}
return 0;
}
CgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8yIiwgInVucm9sbC1sb29wcyIsICJpbmxpbmUiLCAiLWZmYXN0LW1hdGgiKQojcHJhZ21hIEdDQyB0YXJnZXQoImF2eCxzc2UyLHNzZTMsc3NlNCxtbXgiKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGZhc3RpbyBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUobnVsbHB0cik7IGNvdXQudGllKG51bGxwdHIpOwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGludCBsbAojZGVmaW5lIGxkIGxvbmcgZG91YmxlCiNkZWZpbmUgZXBzIDFlLTEyCiNkZWZpbmUgTU9EICgoaW50KTFlOSs3KQppbnQgc3FyKGludCB4KSB7CiAgICBpbnQgbCgwKSwgcih4KTsKICAgIGludCBhKHgpLCBiKCh4ICsgMSkgPj4gMSk7CiAgICB3aGlsZSAoYSA+IGIpCiAgICAgICAgYSA9IGIsIGIgPSAoYiArIHggLyBiKSA+PiAxOwogICAgcmV0dXJuIGE7Cn0KbmFtZXNwYWNlIG5Dcgp7CiAgICBpbnQgZmFzdHBvKGludCBiYXNlLCBpbnQgZXhwKSB7CiAgICAgICAgaW50IGFucyA9IDE7CiAgICAgICAgd2hpbGUoZXhwKQogICAgICAgIHsKICAgICAgICAgICAgaWYoZXhwJjEpIGFucyA9ICgxbGwgKiBhbnMgKiBiYXNlKSAlIE1PRDsKICAgICAgICAgICAgYmFzZSA9ICgxbGwgKiBiYXNlICogYmFzZSkgJSBNT0Q7CiAgICAgICAgICAgIGV4cCA+Pj0gMTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKICAgIH0KICAgIHZlY3RvcjxpbnQ+IGZhYywgaW52LCBmaW52OwogICAgdm9pZCBzeihpbnQgbikgewogICAgICAgIGZhYy5yZXNpemUobiszKSxpbnYucmVzaXplKG4rMyksZmludi5yZXNpemUobiszKTsKICAgICAgICBmYWNbMF09aW52WzBdPWludlsxXT1maW52WzBdPWZpbnZbMV09MTsKICAgICAgICBmb3IoaW50IGkoMSk7IGk8PW47ICsraSkgZmFjW2ldPWZhY1tpLTFdKmklTU9EOwogICAgICAgIGZvcihpbnQgaSgyKTsgaTw9bjsgKytpKSBpbnZbaV09TU9ELU1PRC9pKmludltNT0QlaV0lTU9EOwogICAgICAgIGZvcihpbnQgaSgyKTsgaTw9bjsgKytpKSBmaW52W2ldPWZpbnZbaS0xXSppbnZbaV0lTU9EOwogICAgfQogICAgaW50IEMoaW50IG4sIGludCByKSB7CiAgICAgICAgaWYobjwwIG9yIHI+bikgcmV0dXJuIDA7CiAgICAgICAgcmV0dXJuKGZhY1tuXSpmaW52W3JdJU1PRCpmaW52W24tcl0lTU9EKTsKICAgIH0KfQpjb25zdCBpbnQgQyA9ICgxbGwgPDwgMzApICUgTU9EOwpzdHJ1Y3QgRmVud2lja1RyZWUgewogICAgaW50IHNpemU7CiAgICB2ZWN0b3I8aW50PiB0cmVlOwogICAgRmVud2lja1RyZWUoaW50IG4pIDogc2l6ZShuKSwgdHJlZShuKzEpIHt9CgogICAgdm9pZCBhZGQoaW50IGlkeCwgaW50IGRlbHRhKXsKICAgICAgICB3aGlsZSAoaWR4IDw9IHNpemUpewogICAgICAgICAgICB0cmVlW2lkeF0gKz0gZGVsdGE7CiAgICAgICAgICAgIGlkeCArPSBpZHggJiAtaWR4OwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgcXVlcnkoaW50IGlkeCkgY29uc3R7CiAgICAgICAgaW50IHJlcygwKSwgaShpZHgpOwogICAgICAgIHdoaWxlIChpID4gMCkKICAgICAgICAgICAgcmVzICs9IHRyZWVbaV0sIGkgLT0gaSAmIC1pOwogICAgICAgIHJldHVybiByZXM7CiAgICB9CgogICAgdm9pZCByZXNldCgpewogICAgICAgIGZpbGwodHJlZS5iZWdpbigpLCB0cmVlLmVuZCgpLCAwKTsKICAgIH0KfTsKCnZvaWQgR0VUQUMoKSB7CgogICAgaW50IG4sIGssIGMoMCksIG0sIHEsIHIsIHgsIGYsIGFucygwKTsKICAgIGludCBBLCBCLCBNLCBSLCBDOwogICAgY2luID4+IFIgPj4gQyA+PiBrOwogICAgdmVjdG9yPHZlY3RvcjxwYWlyPGludCwgaW50Pj4+IHZwOwogICAgaW50IG14b3duKDApOwogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBncmlkKFIsIHZlY3RvcjxpbnQ+KEMpKTsKICAgIGZvcihpbnQgaSgwKTsgaSA8IFI7ICsraSl7CiAgICAgICAgZm9yKGludCBqKDApOyBqIDwgQzsgKytqKXsKICAgICAgICAgICAgY2luID4+IGdyaWRbaV1bal07CiAgICAgICAgICAgIGlmKGdyaWRbaV1bal0gPiBteG93bikKICAgICAgICAgICAgICAgIG14b3duID0gZ3JpZFtpXVtqXTsKICAgICAgICB9CiAgICB9CiAgICB2cC5hc3NpZ24obXhvd24rMSwgdmVjdG9yPHBhaXI8aW50LCBpbnQ+PigpKTsKICAgIGZvcihpbnQgaSgwKTsgaSA8IFI7ICsraSl7CiAgICAgICAgZm9yKGludCBqKDApLCBpZHg7IGogPCBDOyArK2opewogICAgICAgICAgICBpZHggPSBncmlkW2ldW2pdLAogICAgICAgICAgICB2cFtpZHhdLmVtcGxhY2VfYmFjayhtYWtlX3BhaXIoaSsxLCBqKzEpKTsKICAgICAgICB9CiAgICB9CiAgICB2ZWN0b3I8dmVjdG9yPHBhaXI8aW50LCBpbnQ+Pj4gcChteG93bik7CiAgICBmb3IgKGludCBvKDEpOyBvIDw9IG14b3duOyArK28pewogICAgICAgIGlmICh2cFtvXS5zaXplKCkgPiAxKXsKICAgICAgICAgICAgc29ydCh2cFtvXS5iZWdpbigpLCB2cFtvXS5lbmQoKSwgWyZdKGNvbnN0IHBhaXI8aW50LGludD4gJmEsIGNvbnN0IHBhaXI8aW50LGludD4gJmIpIC0+IGJvb2x7CiAgICAgICAgICAgICAgICBpZihhLmZpcnN0IF4gYi5maXJzdCkgcmV0dXJuIGEuZmlyc3QgPCBiLmZpcnN0OwogICAgICAgICAgICAgICAgZWxzZSByZXR1cm4gYS5zZWNvbmQgPCBiLnNlY29uZDsKICAgICAgICAgICAgfSk7CiAgICAgICAgICAgIHAuZW1wbGFjZV9iYWNrKHZwW29dKTsKICAgICAgICB9CiAgICB9CiAgICBpbnQgbCgwKSwgaChtYXgoUiwgQykpOwogICAgd2hpbGUgKGwgPCBoKXsKICAgICAgICBtID0gKGwgKyAoKGgtbCkgPj4gMSkpOwogICAgICAgIGludCBzKDApOwogICAgICAgIGZvciAoaW50IGkoMSksIGFpOyBpIDw9IFI7ICsraSl7CiAgICAgICAgICAgIGFpID0gbWluKFIsIGkrbSkgLSBtYXgoMWxsLCBpLW0pICsgMTsKICAgICAgICAgICAgcyArPSBhaTsKICAgICAgICB9CiAgICAgICAgaW50IHNiKDApOwogICAgICAgIGZvcihpbnQgaigxKSwgYmo7IGogPD0gQzsgKytqKXsKICAgICAgICAgICAgYmogPSBtaW4oQywgaiArIG0pIC0gbWF4KDFsbCwgai1tKSArIDE7CiAgICAgICAgICAgIHNiICs9IGJqOwogICAgICAgIH0KICAgICAgICBpbnQgcG90KHMqc2IgLSBSKkMpLCBzYW1lKDApOwogICAgICAgIEZlbndpY2tUcmVlIGZ0KEMpOwogICAgICAgIGZvcihhdXRvICZjZWxsIDogcCl7CiAgICAgICAgICAgIGludCBuKGNlbGwuc2l6ZSgpKSwgbCgwKSwgcigwKTsKICAgICAgICAgICAgZnQucmVzZXQoKTsKICAgICAgICAgICAgZm9yKGludCBpKDApOyBpIDwgbjsgKytpKXsKICAgICAgICAgICAgICAgIGludCBjdXJ4KGNlbGxbaV0uZmlyc3QpLCBjdXJ5KGNlbGxbaV0uc2Vjb25kKTsKICAgICAgICAgICAgICAgIHdoaWxlIChyIDwgbiBhbmQgY2VsbFtyXS5maXJzdCA8PSBjdXJ4K20pCiAgICAgICAgICAgICAgICAgICAgZnQuYWRkKGNlbGxbcl0uc2Vjb25kLCAxKSwgKytyOwogICAgICAgICAgICAgICAgd2hpbGUgKGwgPCBuIGFuZCBjZWxsW2xdLmZpcnN0IDwgY3VyeC1tKQogICAgICAgICAgICAgICAgICAgIGZ0LmFkZChjZWxsW2xdLnNlY29uZCwgLTEpLCArK2w7CiAgICAgICAgICAgICAgICBpbnQgY2wobWF4KDFsbCwgKGludCkoY3VyeS1tKSkpLCBjcihtaW4oKGludClDLCAoaW50KShjdXJ5K20pKSksCiAgICAgICAgICAgICAgICBmKGZ0LnF1ZXJ5KGNyKSAtIGZ0LnF1ZXJ5KGNsLTEpKTsKICAgICAgICAgICAgICAgIHNhbWUgKz0gZi0xOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIChwb3QgPj0gaytzYW1lKT8gaD1tIDogKGw9bSsxLCBhbnMgPSBsKTsKICAgIH0KICAgIGNvdXQgPDwgYW5zOwp9CgoKc3RhdGljIHZvaWQgcnVuX3dpdGhfc3RhY2tfc2l6ZSh2b2lkICgqZnVuYykodm9pZCksIHNpemVfdCBzdHNpemUpIHsKICAgIGNoYXIgKnN0YWNrLCAqc2VuZDsKICAgIHN0YWNrID0gKGNoYXIgKiltYWxsb2Moc3RzaXplKTsKICAgIGlmICghc3RhY2spIHsKICAgICAgICBleGl0KDEpOwogICAgfQogICAgc2VuZCA9IHN0YWNrICsgc3RzaXplIC0gMTY7CiAgICBzZW5kID0gKGNoYXIgKikoKHVpbnRwdHJfdClzZW5kICYgLTE2TCk7CgogICAgYXNtIHZvbGF0aWxlKAogICAgICAgICAgICAibW92ICUlcnNwLCAoJTApXG4iCiAgICAgICAgICAgICJtb3YgJTAsICUlcnNwXG4iCiAgICAgICAgICAgIDoKICAgICAgICAgICAgOiAiciIoc2VuZCkKICAgICAgICAgICAgOiAibWVtb3J5IgogICAgICAgICAgICApOwoKICAgIGZ1bmMoKTsKCiAgICBhc20gdm9sYXRpbGUoCiAgICAgICAgICAgICJtb3YgKCUwKSwgJSVyc3BcbiIKICAgICAgICAgICAgOgogICAgICAgICAgICA6ICJyIihzZW5kKQogICAgICAgICAgICA6ICJtZW1vcnkiCiAgICAgICAgICAgICk7CgogICAgZnJlZShzdGFjayk7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgZmFzdGlvCmZyZW9wZW4oIkQ6XFxNRVRBXFxidW5ueV9ob3BzY290Y2hfaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKCJEOlxcTUVUQVxcT1VUMS50eHQiLCAidyIsIHN0ZG91dCk7CiAgICBpbnQgVDsKICAgIGNpbiA+PiBUOwoKICAgIGZvciAoaW50IHRjKDEpOyB0YyA8PSBUOyArK3RjKXsKICAgICAgICBjb3V0IDw8ICJDYXNlICMiIDw8IHRjIDw8ICI6ICI7CiAgICAgICAgcnVuX3dpdGhfc3RhY2tfc2l6ZShHRVRBQywgMTAyNCAqIDEwMjQgKiAxMDI0KTsKICAgICAgICBjb3V0IDw8ICJcbiI7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0KCg==