#include <bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (int i = (r); i >= (l); --i)
#define FI first
#define SE second
#define SZ size()
using namespace std;
const int N = 1.5e3 + 5;
const int mod = 998244353;
const int inf = 1e18;
int n, T, m, k;
bool mp[N][N], flag;
void print() {
    if (!flag) {
        FOR (i, 1, n) {
            FOR (j, 1, m) {
                if (i > 1 && j > 1) {
                    int sum = mp[i][j];
                    sum += mp[i - 1][j];
                    sum += mp[i - 1][j - 1];
                    sum += mp[i][j - 1];
                    if (sum == 2) {
                        cout << n << m << endl;
                        exit(0);
                    }
                }
                // cout << mp[i][j];
            }
            // cout << '\n';
        }
        return;
    }
    FOR (i, 1, m) {
        FOR (j, 1, n) {
            // cout << mp[j][i];
        }
        // cout << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T --> 0) {
        cin >> n >> m >> k;
        flag = 0;
        PII lst = MP(0, 0);
        if (n < m) {
            swap(n, m);
            flag = 1;
        }
        FOR (i, 1, n) {
            FOR (j, 1, m) {
                mp[i][j] = 0;
            }
        }
        if (!k) {
            print();
            continue;
        }
        if (n == 2 && m == 2 && k == 2) {
            cout << "10\n01\n";
            continue;
        }
        if (!k) {
            FOR (i, 1, 2) {
                FOR (j, 1, 3) {
                    cout << 0;
                }
                cout << '\n';
            }

            continue;
        }
        mp[1][1] = 1;
        --k;
        if (!k) {
            print();
            continue;
        }
        if (k == 1) {
            if (m == 2) {
                mp[3][1] = 1;
            } else {
                mp[1][3] = 1;
            }
            print();
            continue;
        }
        if (k == 2) {
            mp[2][1] = mp[1][2] = 1;
            print();
            continue;
        }
        FOR (i, 3, m) {
            mp[1][i] = 1;
            --k;
            if (!k) {
                break;
            }
            ++i;
        }
        FOR (i, 1, n - 1) {
            FOR (j, 1, m) {
                if (k <= 0 || (j & 1) == (i & 1)) {
                    continue;
                }
                lst = MP(i, j);
                k -= 2;
                mp[i][j] = mp[i + 1][j] = 1;
            }
        }
        if (n & 1) {
            FOR (j, 2, m) {
                if (k <= 0) {
                    break;
                }
                --k;
                mp[n][j] = 1;
                j++;
            }
        } else {
            FOR (j, 1, m) {
                if (k <= 0) {
                    break;
                }
                --k;
                mp[n][j] = 1;
                j++;
            }
        }
        if (k == -1) {
            mp[1][1] = 0;
            ++k;
            if (lst.FI == 1) {
                mp[lst.FI][lst.SE] = mp[lst.FI + 1][lst.SE] = 0;
                mp[2][1] = mp[3][1] = 1;
            }
        }
        print();
    }
    return 0;
}