#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define dbg(x) cerr << (#x) << " --> " << (x) << nl;
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
using namespace std;
#ifdef superset
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree < pair <int, int>, null_type, less < pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#endif
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 350 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int get_int() {
char x = getchar();
bool mns = 0;
while (!isdigit(x)) mns |= x == '-', x = getchar();
int res = 0;
while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
if (mns) res = -res;
return res;
}
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
int mult(int x, int y) {
return x * 1ll * y % mod;
}
int sum(int x, int y) {
add(x, y);
return x;
}
int n, m, k;
int a[N][N];
ll s[N][N];
ll get(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
bool z;
bool corr(int x1, int y1, int x2, int y2, int lvl) {
if (x1 == x2 && y1 == y2) {
return a[x1][y1] <= lvl;
}
rep(i, y1, y2)
if (a[x1][i] > lvl || a[x2][i] > lvl) return 0;
rep(i, x1, x2) {
if (a[i][y1] > lvl || a[i][y2] > lvl) return 0;
}
return corr(x1 + 1, y1 + 1, x2 - 1, y2 - 1, lvl + 1);
}
bool check(int x) {
ll need = 0;
int len = x * 2 - 1;
for (int i = len; i >= 1; i -= 2) {
need += sqr(i);
}
for (int i = 1; i <= n - len + 1; i++) {
for (int j = 1; j <= m - len + 1; j++) {
if (need - get(i, j, i + len - 1, j + len - 1) <= k && corr(i, j, i + len - 1, j + len - 1, 1)) {
return 1;
}
}
}
return 0;
}
void solve() {
n = get_int(), m = get_int(), k = get_int();
memset(s, 0, sizeof(s));
rep(i, 1, n) {
rep(j, 1, m) {
a[i][j] = get_int();
s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
}
}
int l = 1, r = min((n + 1) / 2, (m + 1) / 2), res = 0;
rep(i, l, r)
if (check(i)) res = i;
printf ("%d\n", res);
}
int main() {
#ifdef IOI2018
#define Toktama ""
freopen (Toktama".in", "r", stdin);
//freopen (Toktama".out", "w", stdout);
#endif
int T = 1;
T = get_int();
while (T--)
solve();
ioi
}
I3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9zdGFjazoyMDAwMDAwMCIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJPZmFzdCIpCiNwcmFnbWEgR0NDIHRhcmdldCgic3NlLHNzZTIsc3NlMyxzc2UzLHNzZTQscG9wY250LGFibSxtbXgiKQoKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZAoKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBwcCBwb3BfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgoKI2RlZmluZSBzeih4KSAoaW50KXguc2l6ZSgpCiNkZWZpbmUgc3FyKHgpICgoeCkgKiAxbGwgKiAoeCkpCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQoKI2RlZmluZSByZXAoaSwgbCwgcikgZm9yIChpbnQgaSA9IGw7IGkgPD0gcjsgaSsrKQojZGVmaW5lIHBlcihpLCBsLCByKSBmb3IgKGludCBpID0gbDsgaSA+PSByOyBpLS0pCgojZGVmaW5lIGRiZyh4KSBjZXJyIDw8ICgjeCkgPDwgIiAtLT4gIiA8PCAoeCkgPDwgbmw7CiNkZWZpbmUgS2F6YWtoc3RhbiBpb3NfYmFzZSA6OiBzeW5jX3dpdGhfc3RkaW8oMCksIGNpbi50aWUoMCksIGNvdXQudGllKDApOwoKI2RlZmluZSBubCAnXG4nCiNkZWZpbmUgaW9pIGV4aXQoMCk7Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2lmZGVmIHN1cGVyc2V0CiAgI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgogICNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgogICNpbmNsdWRlIDxleHQvcGJfZHMvZGV0YWlsL3N0YW5kYXJkX3BvbGljaWVzLmhwcD4KCiAgdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CiAgdHlwZWRlZiB0cmVlIDwgcGFpciA8aW50LCBpbnQ+LCBudWxsX3R5cGUsIGxlc3MgPCBwYWlyIDxpbnQsIGludD4gPiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4gb3JkZXJlZF9zZXQ7CiNlbmRpZgoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKCmNvbnN0IGludCBOID0gMzUwICsgNywgaW5mID0gMWU5ICsgNywgbW9kID0gMWU5ICsgNzsKY29uc3QgbGwgbGluZiA9IChsbCkxZTE4ICsgNzsKY29uc3QgaW50IGR4W10gPSB7LTEsIDAsIDEsIDAsIDEsIC0xLCAtMSwgMX0sIGR5W10gPSB7MCwgMSwgMCwgLTEsIDEsIC0xLCAxLCAtMX07CgppbnQgZ2V0X2ludCgpIHsKICBjaGFyIHggPSBnZXRjaGFyKCk7CiAgYm9vbCBtbnMgPSAwOwogIHdoaWxlICghaXNkaWdpdCh4KSkgbW5zIHw9IHggPT0gJy0nLCB4ID0gZ2V0Y2hhcigpOwogIGludCByZXMgPSAwOwogIHdoaWxlIChpc2RpZ2l0KHgpKSByZXMgPSByZXMgKiAxMCArIHggLSAnMCcsIHggPSBnZXRjaGFyKCk7CiAgaWYgKG1ucykgcmVzID0gLXJlczsKICByZXR1cm4gcmVzOwp9CnZvaWQgYWRkKGludCAmeCwgaW50IHkpIHsKICB4ICs9IHk7CiAgaWYgKHggPj0gbW9kKSB4IC09IG1vZDsKICBpZiAoeCA8IDApIHggKz0gbW9kOwp9CmludCBtdWx0KGludCB4LCBpbnQgeSkgewogIHJldHVybiB4ICogMWxsICogeSAlIG1vZDsKfQppbnQgc3VtKGludCB4LCBpbnQgeSkgewogIGFkZCh4LCB5KTsKICByZXR1cm4geDsKfQoKaW50IG4sIG0sIGs7CmludCBhW05dW05dOwpsbCBzW05dW05dOwoKbGwgZ2V0KGludCB4MSwgaW50IHkxLCBpbnQgeDIsIGludCB5MikgewogIHJldHVybiBzW3gyXVt5Ml0gLSBzW3gxIC0gMV1beTJdIC0gc1t4Ml1beTEgLSAxXSArIHNbeDEgLSAxXVt5MSAtIDFdOwp9CmJvb2wgejsKYm9vbCBjb3JyKGludCB4MSwgaW50IHkxLCBpbnQgeDIsIGludCB5MiwgaW50IGx2bCkgewogIGlmICh4MSA9PSB4MiAmJiB5MSA9PSB5MikgewogICAgcmV0dXJuIGFbeDFdW3kxXSA8PSBsdmw7CiAgfQogIHJlcChpLCB5MSwgeTIpCiAgICBpZiAoYVt4MV1baV0gPiBsdmwgfHwgYVt4Ml1baV0gPiBsdmwpIHJldHVybiAwOwogIHJlcChpLCB4MSwgeDIpIHsKICAgIGlmIChhW2ldW3kxXSA+IGx2bCB8fCBhW2ldW3kyXSA+IGx2bCkgcmV0dXJuIDA7CiAgfQogIHJldHVybiBjb3JyKHgxICsgMSwgeTEgKyAxLCB4MiAtIDEsIHkyIC0gMSwgbHZsICsgMSk7Cn0KYm9vbCBjaGVjayhpbnQgeCkgewogIGxsIG5lZWQgPSAwOwogIGludCBsZW4gPSB4ICogMiAtIDE7CiAgZm9yIChpbnQgaSA9IGxlbjsgaSA+PSAxOyBpIC09IDIpIHsKICAgIG5lZWQgKz0gc3FyKGkpOwogIH0KICBmb3IgKGludCBpID0gMTsgaSA8PSBuIC0gbGVuICsgMTsgaSsrKSB7CiAgICBmb3IgKGludCBqID0gMTsgaiA8PSBtIC0gbGVuICsgMTsgaisrKSB7CiAgICAgIGlmIChuZWVkIC0gZ2V0KGksIGosIGkgKyBsZW4gLSAxLCBqICsgbGVuIC0gMSkgPD0gayAmJiBjb3JyKGksIGosIGkgKyBsZW4gLSAxLCBqICsgbGVuIC0gMSwgMSkpIHsKICAgICAgICByZXR1cm4gMTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gMDsKfQp2b2lkIHNvbHZlKCkgewogIG4gPSBnZXRfaW50KCksIG0gPSBnZXRfaW50KCksIGsgPSBnZXRfaW50KCk7CiAgbWVtc2V0KHMsIDAsIHNpemVvZihzKSk7CiAgcmVwKGksIDEsIG4pIHsKICAgIHJlcChqLCAxLCBtKSB7CiAgICAgIGFbaV1bal0gPSBnZXRfaW50KCk7CiAgICAgIHNbaV1bal0gPSBzW2kgLSAxXVtqXSArIHNbaV1baiAtIDFdICsgYVtpXVtqXSAtIHNbaSAtIDFdW2ogLSAxXTsKICAgIH0KICB9CiAgaW50IGwgPSAxLCByID0gbWluKChuICsgMSkgLyAyLCAobSArIDEpIC8gMiksIHJlcyA9IDA7CiAgcmVwKGksIGwsIHIpCiAgICBpZiAoY2hlY2soaSkpIHJlcyA9IGk7CiAgcHJpbnRmICgiJWRcbiIsIHJlcyk7Cn0KaW50IG1haW4oKSB7CiAgI2lmZGVmIElPSTIwMTgKICAgICNkZWZpbmUgVG9rdGFtYSAiIgogICAgZnJlb3BlbiAoVG9rdGFtYSIuaW4iLCAiciIsIHN0ZGluKTsKICAgIC8vZnJlb3BlbiAoVG9rdGFtYSIub3V0IiwgInciLCBzdGRvdXQpOwogICNlbmRpZgogIGludCBUID0gMTsKICBUID0gZ2V0X2ludCgpOwogIHdoaWxlIChULS0pCiAgICBzb2x2ZSgpOwogIGlvaQp9