#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
#define x first
#define y second
#define pii pair<int,int>
int n, m, q, idlim;
int idh(int x, int y) {
return x * (m + 2) + y;
}
pii hdi(int id) {
return pii(id / (m + 2), id % (m + 2));
}
int idv(int x, int y) {
return y * (n + 2) + x;
}
pii vdi(int id) {
return pii(id % (n + 2), id / (n + 2));
}
template<class T>
struct array2d {
T a[N];
int n, m;
void init(int val = 0) {
memset(a, val, sizeof(a));
}
void set_size(int n, int m, int val = 0) {
this->n = n;
this->m = m;
init(val);
}
T *operator[](int i) {
return a + i * (m + 2);
}
const T *operator[](int i)const {
return a + i * (m + 2);
}
T &operator[](pii p) {
return a[p.x * (m + 2) + p.y];
}
const T &operator[](pii p)const {
return a[p.x * (m + 2) + p.y];
}
};
array2d<int> v, h, col, lv, tim;
vector<pii> piece;
struct node {
int ch[2], sz;
};
node t[N * 30];
int cnt;
void pushup(int x) {
t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz;
}
void insert(int p, int &x, int l, int r) {
if (!x)
x = ++cnt;
if (l == r) {
t[x].sz = 1;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
insert(p, t[x].ch[0], l, mid);
else
insert(p, t[x].ch[1], mid + 1, r);
pushup(x);
}
void erase(int p, int &x, int l, int r) {
if (!x)
return;
if (l == r) {
t[x].sz = 0;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
erase(p, t[x].ch[0], l, mid);
else
erase(p, t[x].ch[1], mid + 1, r);
pushup(x);
}
int merge(int x, int y) {
if (!(x && y))
return x + y;
t[x].ch[0] = merge(t[x].ch[0], t[y].ch[0]);
t[x].ch[1] = merge(t[x].ch[1], t[y].ch[1]);
if (t[x].ch[0] || t[x].ch[1])
pushup(x);
else
t[x].sz |= t[y].sz;
return x;
}
int query_rk(int v, int x, int l, int r) {
if (!t[x].sz)
return 0;
if (l == r)
return t[x].sz;
int mid = (l + r) >> 1;
if (v <= mid)
return query_rk(v, t[x].ch[0], l, mid);
else
return t[t[x].ch[0]].sz + query_rk(v, t[x].ch[1], mid + 1, r);
}
bool exist(int v, int x, int l, int r) {
if (!t[x].sz)
return 0;
if (l == r)
return 1;
int mid = (l + r) >> 1;
if (v <= mid)
return exist(v, t[x].ch[0], l, mid);
else
return exist(v, t[x].ch[1], mid + 1, r);
}
struct DSU_with_lr {
int l[N], r[N], f[N];
int _(int x) {
return f[x] == x ? x : f[x] = _(f[x]);
}
void merge(int x, int y) {
x = (x), y = (y);
if (x == y)
return;
f[x] = y;
l[y] = min(l[y], l[x]);
r[y] = max(r[y], r[x]);
}
int getl(int id) {
return l[(id)];
}
int getr(int id) {
return r[(id)];
}
bool check(int x, int y) {
return _(x) == _(y);
}
};
DSU_with_lr hseg, vseg;
struct block {
int rt0, rt1, rth, rtv;
void merge(block &y) {
rt0 =::merge(rt0, y.rt0);
rt1 =::merge(rt1, y.rt1);
rth =::merge(rth, y.rth);
rtv =::merge(rtv, y.rtv);
}
int get0(int v) {
return query_rk(v, rt0, 1, q);
}
void ins0(int v) {
insert(v, rt0, 1, q);
}
void era0(int v) {
erase(v, rt0, 1, q);
}
int get1(int v) {
return query_rk(v, rt1, 1, q);
}
void ins1(int v) {
insert(v, rt1, 1, q);
}
void era1(int v) {
erase(v, rt1, 1, q);
}
void ins01(int col, int v) {
col ? ins1(v) : ins0(v);
}
void era01(int col, int v) {
col ? era1(v) : era0(v);
}
void insp(int x, int y) {
insert(idh(x, y), rth, 1, idlim);
insert(idv(x, y), rtv, 1, idlim);
}
int getsz(int col, int lv) {
return t[rth].sz + (1 - col ? get1(lv) : get0(lv));
}
int geth(int x, int y1, int y2, int colx, int lvx) {
auto check = [&](int p, int q) {
return col[p][q] == 1 - colx && lv[p][q] <= lvx && exist(lv[p][q], 1 - colx ? rt1 : rt0, 1, ::q);
};
return query_rk(idh(x, y2), rth, 1, idlim) - query_rk(idh(x, y1 - 1), rth, 1, idlim)
+ (h[x][y1 - 1] == 2 && check(x, y1 - 1)) + (h[x][y2] == 2 && check(x, y2 + 1));
}
int getv(int x1, int x2, int y, int colx, int lvx) {
auto check = [&](int p, int q) {
return col[p][q] == 1 - colx && lv[p][q] <= lvx && exist(lv[p][q], 1 - colx ? rt1 : rt0, 1, ::q);
};
return query_rk(idv(x2, y), rtv, 1, idlim) - query_rk(idv(x1 - 1, y), rtv, 1, idlim)
+ (v[x1 - 1][y] == 2 && check(x1 - 1, y)) + (v[x2][y] == 2 && check(x2 + 1, y));
}
};
template<class T>
struct DSU_array2d {
array2d<T>a;
array2d<pii>f;
void init(int val = 0) {
a.init(val);
}
void set_size(int n, int m, int val = 0) {
a.set_size(n, m, val);
f.set_size(n, m, val);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = {i, j};
}
pii _(pii x) {
return x == f[x] ? x : f[x] = (f[x]);
}
T &operator[](pii p) {
return a[(p)];
}
void merge(pii x, pii y) {
x = _(x), y = _(y);
if (x == y)
return;
a[x].merge(a[y]);
f[y] = x;
}
};
DSU_array2d<block> b;
int qsum = 0;
int ans[N];
int lvcnt[N];
void mian() {
cin >> n >> m >> q;
v.set_size(n, m);
h.set_size(n, m);
col.set_size(n, m, -1);
lv.set_size(n, m);
tim.set_size(n, m);
piece.clear();
memset(t, 0, sizeof(t));
memset(&hseg, 0, sizeof(hseg));
memset(&vseg, 0, sizeof(vseg));
memset(lvcnt, 0, sizeof(lvcnt));
b.set_size(n, m);
for (int i = 0; i < N; i++)
hseg.l[i] = hseg.r[i] = hseg.f[i] = i;
for (int i = 0; i < N; i++)
vseg.l[i] = vseg.r[i] = vseg.f[i] = i;
idlim = (n + 3) * (m + 3);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
mian();
}
}
