// #Team4T's full template, by AkiLotus.
// Powered by Alice Engine.
// File name: 1955G.cpp
// Time created: Tue Apr 09 2024 00:19

/************************************************ [OPTIMIZATION PROTOCOL] ************************************************/
#pragma GCC optimize("Ofast")
#ifndef Alice
#pragma GCC target("arch=skylake")
#endif
/*************************************************************************************************************************/

/************************************************ [  LIBRARY PROTOCOL   ] ************************************************/
#include <bits/stdc++.h>
using namespace std;
/*************************************************************************************************************************/

/************************************************ [  LEGENDS/CONSTANTS  ] ************************************************/
#define endl '\n'
#define i64 long long
#define ld long double
const long double PI = 3.141592653589793116L;
const long double GOLD = ((1.0L+sqrt(5.0L))/2.0L);
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
/*************************************************************************************************************************/

/************************************************ [      SOLUTION       ] ************************************************/
int MultiTest = 1;
int n, m; vector<vector<int>> a;

void Preprocess() {
    
}

void Input(int testcase) {
    cin >> n >> m; a.clear(); a.resize(n, vector<int>(m));
    for (auto &row: a) {
        for (auto &z: row) cin >> z;
    }
}

void Solve(int testcase) {
    int candidate = __gcd(a[0][0], a[n-1][m-1]);
    set<int> divisors;
    divisors.insert(candidate);
    for (int i=2; i*i<=candidate; i++) {
        if (candidate % i != 0) continue;
        divisors.insert(i);
        divisors.insert(candidate / i);
    }

    int ans = 1;
    for (auto it=divisors.rbegin(); it!=divisors.rend(); it++) {
        int d = *it;
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pair<int, int>> q;
        q.push({0, 0}); visited[0][0] = true;
        while (!q.empty()) {
            auto [i, j] = q.front(); q.pop();
            if (i + 1 < n && !visited[i+1][j] && a[i+1][j] % d == 0) {
                visited[i+1][j] = true; q.push({i+1, j});
            }
            if (j + 1 < m && !visited[i][j+1] && a[i][j+1] % d == 0) {
                visited[i][j+1] = true; q.push({i, j+1});
            }
        }
        if (visited[n-1][m-1]) {ans = d; break;}
    }
    cout << ans << endl;
}
/*************************************************************************************************************************/

/************************************************ [        MAIN         ] ************************************************/
int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false);
    
    Preprocess();
    
    int T = 1; if (MultiTest) {cin >> T; cin.ignore();}
    for (int testcase=1; testcase<=T; testcase++) {Input(testcase); Solve(testcase);}
    
    return 0;
}
/*************************************************************************************************************************/

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢥⢼⣞⣬⡑⢎⣹⣏⠁⡨⠣⠰⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠑⠍⡙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢋⣺⢗⣪⣧⢼⣻⡯⡽⢾⣯⣟⣺⡟⢫⡯⣟⣶⣙⡆⡀⡀⡀⡀⡀⡀⡀⡀⠓⣈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⡗⣥⣿⡿⣛⣺⡯⢽⣞⣯⣝⡮⣽⠿⠋⡁⡀⡀⠂⡀⠑⡀⠂⡀⡀⡀⡀⡀⡀⡀⠳⡄⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⡯⣼⣿⡟⢾⠵⣢⣾⡿⣿⣿⢿⣿⢁⢊⢘⠁⣨⠊⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⡦⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣽⣜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⡽⣽⣱⢫⣳⢽⢙⣾⣿⣋⣺⣿⣿⣿⡀⡂⢁⢀⣐⡻⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⡀⡀⡀⠙⠉⠢⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⡆⣿⣬⣿⣯⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣼⣽⣺⣷⡯⣯⡝⣵⣛⣋⣲⣿⣿⣿⣛⠟⣤⣺⣾⣻⣇⣷⠢⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣄⡀⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣶⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣼⣽⣿⣿⢹⢅⡿⣝⢗⣿⣟⣿⣿⠋⠔⣴⡟⣾⢵⣭⠟⡴⠁⠢⠄⢪⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢳⣣⣤⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⡁⢿⣷⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢱⢣⣿⣿⡏⠍⡟⣮⣎⣿⣿⢿⡿⡠⠅⣾⢋⣿⣻⡷⣡⠏⠎⠃⡐⢑⠎⠄⡃⡀⡀⡀⡀⠢⣇⡀⡀⡀⡀⢀⡀⡀⢷⣿⣧⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⢻⣿⡌⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠯⡟⣿⣿⣿⡜⡾⣜⣕⡾⠁⢀⣾⣧⠁⣾⣋⣽⣟⡿⣰⡣⡴⠂⢆⠊⢸⢐⡢⠈⡀⡀⡀⡀⡀⢿⡀⡀⡀⡀⡀⡀⡀⡀⣿⣷⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣾⣿⣿⢱⢏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣸⣸⢱⣿⢇⢰⢱⣗⣿⡀⢀⣿⣟⢿⢼⢵⡷⣵⣷⣰⢃⣰⠈⢆⡀⢀⣿⠄⠰⠢⠆⡀⠂⡀⡀⠘⡀⡀⡀⡀⡀⡀⡀⡀⠈⣿⢸⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣮⠻⣿⡇⣻⢻⣿⣿⣿⣿⣿⣿⣿⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⡏⡏⣿⣿⡎⢇⣝⣻⡇⡀⣿⣿⡟⣟⣽⣿⣸⣿⢡⡱⣴⠁⡜⠃⢀⣿⢺⢢⠢⢅⢐⡀⡇⡂⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⡸⣿⣿⣿⣧⠉⡇⠸⣿⣹⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣸⢠⢀⣿⡗⣯⢺⡿⣗⠅⢠⣿⣿⣼⠅⣿⣿⣿⢏⣱⡰⠃⡀⠃⣈⠟⢣⡘⡀⡆⠁⡀⠄⡅⢇⡀⡀⢰⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
⡇⣿⣇⣷⣿⡈⠡⠣⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⢮⡟⢢⣾⡺⢺⠇⣷⠁⢸⡟⢣⡟⣪⡯⡃⣿⠂⡵⡞⡀⡀⡿⠁⢀⣼⡇⡀⡇⡀⡇⡊⡇⢸⡀⡀⡌⡀⢀⡀⡀⢠⡀⠈⡀⡀⡀⢘⢣⡀⢿⣿⣿⣿⣿⣿⣿⣿
⣇⣸⣾⣿⣿⡟⡔⠂⢻⣿⡺⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢈⡱⢎⡩⡿⡿⣿⡀⣿⡀⣿⢘⡟⣾⣯⣽⢪⡟⡾⣺⡀⡀⠈⡀⢠⠇⢀⢠⡀⡇⣾⠃⠑⡇⢸⡀⠈⡇⡀⢸⡀⡀⢸⡀⡀⡀⢀⡀⢸⡀⠹⣄⠙⣿⣿⣿⣿⣿⣿
⣿⣿⢨⣿⣿⣿⠙⣧⢀⢻⣧⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢸⣇⣘⣴⣳⢘⣿⢠⢿⡀⣷⣫⠟⣿⡺⡻⣸⡇⢇⠇⡀⡐⠔⣠⡝⡀⡺⠎⡀⡇⣷⢸⠈⡇⢸⡀⡀⡀⡀⣝⡀⠇⣿⡇⡀⡀⢸⡀⢸⢆⠁⠹⣿⣶⣽⣿⣿⣿⣿
⣿⣏⣸⣿⣿⢿⡧⠘⣧⡄⢿⣎⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡇⣱⡇⡯⡏⣼⣿⣨⣞⣭⠿⣋⣾⠇⣡⢯⢼⠁⢸⡀⡀⠥⡼⡍⢠⠸⠃⡰⡀⠃⠃⠏⠄⡀⣾⡀⡸⡀⡀⡛⡀⡀⠿⣿⣤⡀⣸⡀⢸⡃⣦⡀⠙⣿⣿⣿⣿⣿⣿
⣿⠹⣿⡿⣿⡦⢿⢣⢻⡸⢈⢿⣮⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡇⡥⣗⢻⠅⡏⢸⠨⣦⠐⢹⣼⢫⢣⣿⡣⢸⢸⣿⡀⠁⡼⠞⠴⠇⢜⢐⠿⢸⡀⢰⡀⠈⡀⢿⡀⡀⡸⡼⠾⡀⠾⢾⣽⣿⢠⠅⠎⢸⠇⡏⣦⠡⠳⢿⣿⣿⣿⣿
⣿⡇⢹⣿⣿⡟⣿⢓⣼⣻⢫⠂⣿⣜⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡇⣇⢭⡜⡀⡇⠸⡀⣱⣉⣵⣱⡽⣾⣻⣎⠸⡇⡏⡀⢋⢃⣒⡀⡠⡉⠚⣳⡎⡄⢁⠨⠨⢐⣺⡀⠁⠁⢋⠄⣠⣁⣉⢉⠃⡀⠞⠂⡇⢀⡇⣿⣿⣿⣦⣙⣿⣿⣿
⣿⣿⢲⣿⣿⣿⣾⣇⡸⣝⣎⣎⡜⣿⣎⣿⣿⣿⣿⣿⣿⣞⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠄⣿⢸⠑⡀⡇⡀⣗⣠⣿⡾⡕⣼⣿⡼⢫⣕⣧⣏⡎⣿⠁⢰⡜⢠⣿⣿⣶⠠⡀⡰⡔⡘⠢⡇⡞⡀⡇⢻⠜⣿⢿⡇⡟⢀⢀⢇⡀⢸⠄⡃⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⡞⡌⣿⣿⣿⣿⢜⣏⠞⡯⣗⢳⣿⡼⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡇⣿⡀⡆⡀⣷⡀⣏⡏⡀⡼⠘⡎⣏⣷⣇⣻⡽⢸⢸⣌⢛⠶⣖⣛⡹⣬⠁⣾⡀⢣⡀⠃⠏⡇⢀⣯⣣⠤⣟⠯⡪⢧⢁⠃⢸⠏⡀⣿⡆⢸⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣷⣿⣏⣯⣿⣟⣷⣻⠐⠽⡹⡕⣿⣿⣟⣿⣿⣿⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⢸⢻⡄⣿⡀⢸⡀⠸⣝⡌⢐⠐⣷⣿⠹⣿⣍⠳⣧⡀⡄⣿⣤⣓⢜⡝⣗⢾⡇⡀⡀⣨⠏⡼⢰⣿⣻⣞⣻⣟⡾⣳⡵⠁⡸⠃⣼⢀⣿⢸⣼⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡜⣿⣿⣿⣦⢿⠐⠨⣷⣯⠍⣿⣿⡽⢿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠠⡆⣿⠘⣿⡀⡄⡀⡆⠳⣓⣦⢻⡸⡀⠹⣿⣶⡈⢆⠈⠻⣿⣿⣿⣷⡫⣞⡥⡀⠜⠔⣼⡇⣹⡻⣫⣝⣪⣽⡪⠈⡔⠠⡀⣾⠃⣾⣿⡂⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣷⣿⣿⣻⢿⣧⢧⠤⢿⠸⣟⡄⡿⣿⣿⣻⣿⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⢻⡀⢷⠘⣿⡹⠘⠘⠠⢠⠛⠈⣷⡇⡀⠘⣧⡯⢦⡀⠦⡹⣿⣿⡿⡣⣪⠟⠤⢁⡾⢾⠂⡗⢷⢏⢽⣿⣲⢎⠞⢀⣢⣿⣏⣺⣿⢇⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⢹⣻⡗⣷⣿⣧⢧⡮⡧⢳⢿⡈⣝⣿⣿⢿⣿⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣿⣮⣝⣄⠻⣧⡀⠳⡀⠣⡀⢿⣿⡀⡀⡀⢿⣿⣯⣆⢌⢿⣿⣿⢟⣥⣡⣾⣟⢝⣿⣼⡺⢹⢾⣮⢽⠷⢁⣨⣾⣿⣿⣳⣿⢟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⡧⣿⣷⢾⣿⣿⣧⢫⣧⣜⡧⢛⣜⣵⣿⣿⡻⣿⣿⣿⣿⣿⣞⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣳⡀⠙⣄⡀⠙⣿⡆⡀⡀⠠⡙⠿⣿⣷⡤⠙⢷⡮⢝⣫⣗⢗⣺⣺⣾⡯⢾⣗⡲⣻⣏⢏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣷⣎⣷⣇⣿⣿⣿⣦⢞⡼⡺⣇⡄⠊⣿⣿⣿⡻⣿⣿⣿⣿⣿⣜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢿⣿⣿⢋⢿⢲⢷⣤⣿⣿⢸⡄⡀⢸⠨⣅⢉⡯⣙⣶⣍⡳⢯⡗⡪⢽⣻⣯⣽⣳⣏⡵⢏⢟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⢿⢹⣿⡞⣿⣿⣿⡔⣻⢷⢟⣶⢄⡀⢿⣿⣷⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⣿⡘⢸⠇⢻⢹⣾⡄⣿⡀⠸⢄⢿⣷⠸⢲⢮⣹⣕⣝⢧⡾⡯⣯⡶⣖⣽⡻⠓⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣺⣺⣿⣿⣿⣿⣿⣯⠣⣿⡕⢪⡽⠿⣤⡿⣿⣷⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣏⢯⢸⣿⠃⡼⢸⠈⣧⣷⣧⣿⡀⡀⡀⠉⠿⣧⡱⢯⢗⣕⢵⡳⣻⢗⡫⣺⣮⣿⠋⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣧⢺⣿⢎⣧⢾⣸⣗⣮⢿⣿⣿⣯⢿⣿⣿⣾⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣫⣿⣿⠁⣼⠃⣃⡰⠟⣾⣿⢻⡆⡀⠻⣄⡐⡠⠉⠫⣮⣺⡷⡮⢝⢽⡺⣾⠋⡀⣸⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣧⠸⡪⡝⡮⢿⡈⢯⣧⡽⣿⣿⣿⡿⣿⣿⣯⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢈⣴⣷⣟⣟⣿⢸⡌⣿⡘⡀⡀⠃⡀⠈⠱⡢⢕⡂⡉⠓⡛⠮⡽⠟⠠⡀⡀⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⢻⣿⣿⣷⡳⢟⣎⡎⡹⡳⡢⡺⡻⣿⣿⣿⣯⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣭⣿⢿⣿⣵⡿⠫⠘⠚⢿⡇⡀⡀⢀⠐⡀⠑⣀⠃⡄⠂⢸⣿⣿⣹⡜⡀⡀⡀⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⠹⣿⣿⡟⡕⢟⡮⠣⢜⣮⣄⠻⣳⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡾⠛⠛⢉⠚⢀⣰⠟⡀⡀⡀⡁⡀⡀⡀⢄⡀⠁⡀⠑⢢⡂⣿⣿⣿⡿⣷⡀⢥⢀⠈⣿⣿⣿⣿⢿⣿⣻⣷⣟⣼⢿⣿⠟⣾⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣿⣿⣿⣇⣦⢺⣾⣿⠽⣗⣇⡙⡇⡱⢇⡻⣦⣬⡿⣿⣿⣿⣿⣽⣻⡻⣻⣿⣿⣿⣿⣿⣿⣿⠟⠉⠠⠂⢠⠊⡀⡀⡀⡀⡀⡀⡀⡀⣇⡀⡀⠄⠄⠉⡀⠂⡀⡀⡀⠄⠻⣿⣿⣿⠃⢽⣼⢠⣏⣿⣿⣿⣋⣾⣠⢰⢸⢝⣧⣿⣾⡿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡌⡦⢾⡿⣻⣽⣿⡹⢮⡕⢇⡎⢬⣦⡛⠿⣿⣿⣿⣿⣷⣿⡻⣎⣿⣿⣿⣿⣿⣤⣤⡠⣄⠜⡀⡀⡀⡀⡀⡀⢀⠠⠂⡎⢸⡀⡀⠡⡀⡀⢀⡀⡀⡀⡀⡀⡀⠈⠻⣿⡆⣼⢿⡆⣌⣿⣿⣭⢢⠇⣽⠛⡄⡕⠸⣕⣐⣱⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢷⢳⡯⠯⣿⣿⡯⢪⡞⣻⡺⠷⢮⣏⡻⡲⢆⢙⢿⣿⣿⣿⣜⣜⣿⣿⣿⣿⣿⣿⡇⢮⡀⡀⡀⡀⡀⡀⡀⡀⡀⠉⢧⡼⡀⡇⠐⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⢿⡸⢯⣇⣿⣿⣿⠌⡗⣯⣦⢴⣫⡆⣴⣿⣏⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣕⡢⢿⢳⢻⡿⣞⢹⢝⢱⡑⢭⣭⣞⣮⡩⢾⣻⣦⠻⣿⣷⣿⣿⣴⣿⣿⣿⣿⠏⣴⠉⡀⡀⡀⡀⡀⡀⡀⢠⡀⢀⡀⣇⡇⠸⠠⠠⡀⡀⡀⠄⡀⠉⠒⡀⡀⡀⡀⡀⠈⢷⡼⣸⣋⠿⣦⣈⠿⡾⢧⣩⣾⢁⣾⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡎⡪⡧⢎⡻⣻⡸⢽⡯⢸⢪⡕⣹⣓⢎⡪⡺⢯⡝⢦⠚⣿⣿⣿⣷⡻⡿⢡⠋⡀⡀⡀⣠⠎⡀⡀⡀⣠⡿⡀⡀⢰⡀⠇⡀⠆⡀⡀⡀⡀⡀⡀⠁⠸⡆⠠⡀⡀⡀⡀⡀⠉⣿⣟⡓⣖⡵⣴⡿⠉⠲⣨⠍⠋⡾⠿⠿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡿⣳⡎⣎⣜⣻⢯⡳⡳⢣⢼⡶⡃⢵⣗⡱⡮⢕⡫⠽⣀⣞⠛⣿⣿⣿⣄⡀⢸⠨⢝⣰⠃⡀⡀⡀⡴⠁⣠⠶⢛⣩⠽⢻⠛⠈⢇⡀⡀⡀⡀⡀⡀⡀⢿⡄⠑⡀⡀⡀⡀⡀⠈⡿⠿⠽⡋⠤⣈⡥⠉⣾⡀⠉⠛⣷⣄⡀⠹⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢘⢻⣿⢸⡱⣖⣷⣕⣻⢳⣏⣺⣥⠖⠭⢏⣻⣎⣱⢸⡿⡪⢮⢮⣍⣟⣿⡞⣘⣇⣷⠁⡀⡀⡀⡀⣾⠏⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⠸⡀⠡⡀⡀⡀⠌⡀⢻⣿⣿⣿⣿⡉⣴⣿⣿⡀⡀⡀⠘⣿⣿⣔⡻⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⡄⢼⢿⣧⣷⢿⣹⡜⡇⢿⢩⠭⣩⣦⡵⡎⢸⢜⢣⡮⣟⡇⡝⣝⣮⣷⣍⢷⣎⣿⠁⡀⡀⡀⡀⢞⠁⡀⡀⡀⡀⡀⡀⡀⢧⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣇⠥⡀⡀⡀⡀⡀⡀⡀⠻⣿⣿⣯⣿⠛⣛⠿⡀⠁⢙⠁⣿⣿⣿⣿⣌⢻⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢻⡇⢣⣕⢷⢯⢝⣻⣻⢸⡮⣧⡼⢳⡮⢽⣮⣵⡪⢼⣛⡙⢍⡜⡪⠹⡬⠻⣿⢝⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⠐⠈⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⡀⡄⡄⡀⡀⢀⡀⡀⡀⠂⣿⣿⠇⡀⡀⣠⣿⣄⠈⢐⠿⣿⣿⣿⣿⣧⢻⣿
⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣿⣇⣚⡪⡎⡎⢬⣷⣧⢼⣣⣮⢝⡱⢾⣻⢕⢢⠿⣛⡳⡍⢱⣚⡵⠭⢕⡿⣟⣷⠹⡸⡄⡀⡀⡀⡀⡀⡀⡀⡀⢀⡁⠌⡀⠱⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⢢⢸⡇⡀⡀⡀⠈⠑⡀⡀⠹⣿⡀⡀⣾⣿⣿⠡⠰⡀⢸⢸⣿⣿⣿⣿⢸⣿
⣿⣿⣿⣧⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢿⢽⢗⣱⢽⣿⢺⣏⢻⣆⡯⡓⡜⡓⢪⣕⡫⠵⡜⣽⢧⡪⢜⡮⢲⡖⣮⡙⣿⠿⡆⣇⠇⠠⡀⡀⡀⡀⡀⡀⡀⡣⡀⡀⡀⠇⠱⡀⡀⡀⡀⡀⡀⡀⢀⡀⢣⡀⡇⡀⠨⡀⡀⡀⡀⡀⢀⡇⢀⣿⣿⣿⢁⣓⡇⡸⢸⠆⣆⡸⣿⣿⣸⣿
⣿⣿⣿⣿⡌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣌⠲⡺⢯⣷⣇⣝⡳⢻⡌⡺⢹⣎⡸⢵⢎⡱⣇⠨⢕⡪⢆⡬⣵⡵⡢⡙⡏⣣⣿⢸⡀⠐⠃⡀⡀⡀⢀⢫⣸⠁⡀⡀⢀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⡀⡇⠃⡀⡄⡀⡀⡀⡀⠁⢧⣿⣿⡿⡰⢧⡾⡀⡧⣨⢀⡀⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣷⣎⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣓⣯⣾⢫⢽⢧⢧⡜⡻⢳⣎⡸⡏⡕⣾⡡⢝⡪⢫⢫⢇⣜⣿⣇⢸⢿⢸⠸⡀⢐⡀⡀⢠⢲⡪⢥⡀⡀⡀⡀⠃⡀⡀⡀⡀⡀⡀⡀⠠⡀⡀⡀⠸⡀⡷⠐⡀⠰⡀⡀⡀⡀⡀⡀⣿⡿⣗⣺⢂⡀⡀⡎⢋⡞⣰⣠⠢⢀⣿⣿
⣿⣿⣿⣿⣿⢸⡦⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣶⡹⢟⢽⣳⢒⢌⡜⣳⡎⢜⡣⢜⣜⡳⡎⢢⢺⡧⣞⣶⡍⢉⢸⣿⡾⡀⡀⠨⡀⡀⡏⣹⣷⠁⡀⡀⡀⢐⡀⡀⡀⡀⡀⡀⡀⡀⠐⡀⡀⡀⡀⡀⡇⢀⡀⡀⡀⡀⡀⡀⠨⠘⠘⣧⡿⡇⡀⡢⢀⠉⡞⠳⡰⢌⡴⠙⠿⣿
⣿⣿⣿⣿⣿⡗⣻⢾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣽⣿⣷⣿⣶⡘⢜⣻⡣⢼⣏⣳⡯⢱⡧⢜⡕⢎⡣⢜⡜⡵⠟⡖⢪⠸⣾⠁⡀⡀⠐⡀⡀⢵⣎⠃⡀⠠⡀⡀⠂⡀⡀⡀⡀⡀⡀⡀⡀⡀⠄⡀⡀⡀⡀⡇⠂⡀⡀⡄⡀⡀⡀⡀⠂⠳⢿⡏⢸⡪⡀⠊⢠⢟⣿⠖⠉⣽⣿⡷⢼
⣿⣿⣿⣿⣿⣷⡿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣷⣻⣿⣿⣿⣷⣙⢟⡍⢌⡮⡳⡻⢯⢜⢪⢎⣝⣎⣹⢐⢊⡱⣪⡵⠻⡀⡀⠆⠈⡀⢀⢇⡟⡀⠠⠄⡀⢀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⡀⡀⡀⠈⡇⡍⠅⣀⣾⣟⡷⢁⣶⣿⣿⣿⣕⣸
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣏⣿⡼⣿⣿⣿⣿⣿⣷⣝⢕⡸⡎⢻⡩⠭⠆⢱⡗⢯⡟⡢⡜⡕⢸⡀⠂⡀⡀⠃⡀⡀⣸⣺⡀⡀⡼⡇⢀⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⡀⡀⡀⡀⡀⡀⠄⡀⡀⢘⡀⡀⡀⡀⡀⡎⡀⡧⠪⢰⣷⣾⣩⣶⣟⣷⣿⢽⢏⡿⠸
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢿⣿⢿⣿⣿⣿⣿⣿⣾⣷⣕⢿⣧⡜⣣⣇⡢⡯⢭⠇⠡⠅⣇⣸⢀⡀⡀⡀⡂⡀⡀⠹⠏⡀⣰⡊⠃⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠅⡀⡀⡀⡀⢸⡀⡂⡀⡀⡀⡀⡀⡀⡀⡀⠘⣣⠸⠈⣿⢿⣾⣟⣿⣿⢯⢫⢝⣳⣱⣳
⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⢿⣏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣌⢎⣝⣜⡊⣇⣯⡀⢅⡅⢵⢼⠐⡀⡀⡀⢹⡀⡀⡀⡀⠂⡣⡞⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠁⡀⡀⡀⡀⡀⡀⡀⢀⡀⢝⡀⡇⢏⣟⣿⣿⢟⡟⢫⣝⢯⢕⡳⣺
⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣎⡛⣿⣿⣿⣿⣷⣉⢚⡀⣗⡏⡀⢝⡇⠊⠐⡀⠄⡀⡀⢂⡀⡀⡀⡀⢔⠘⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡌⡀⡀⡀⠰⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠉⠄⣦⢸⡣⡧⣿⢯⡿⢜⡧⢝⢇⡼⣳⠫
⣿⣿⣿⣿⣿⣿⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡰⡉⠿⣿⣿⣿⣷⡑⢕⡱⠁⡎⡇⡀⡀⠠⡀⡀⡀⠈⡀⡀⡀⢃⠅⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣰⡀⡀⡀⡀⡂⡀⡀⡀⢀⡀⡀⡀⡀⡀⠈⢄⡀⢺⢸⡊⢿⡟⡯⠵⡳⣫⢳⢮⡊⢱⢃
⣿⣿⣿⣿⣿⣿⡸⣻⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣃⠂⠙⢿⣿⣿⣆⠚⠑⡏⡣⡀⡀⠎⡀⡀⡀⡀⡀⡠⣅⣰⡀⠈⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⡀⡀⡀⡀⠅⡀⢐⡀⢐⡀⡀⡀⡀⡀⡀⡀⠢⢀⢸⡎⢸⣱⠵⣎⡪⢝⢝⢞⡅⠂⣿
⣿⣿⣿⣿⣿⣿⡇⣺⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢦⡀⠙⢿⣿⣿⣦⠹⢿⡀⠈⡀⡀⡀⡀⡀⠌⡀⡀⡀⠈⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⠠⡀⡀⡀⡀⡀⡀⡀⢀⣞⡣⢜⢳⣜⢃⢨⣸⡍⠸⡃⣛⣾
⣿⣿⣿⣿⣿⣿⡇⢽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢦⡙⢤⡈⠻⣝⠿⣦⡀⠅⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠐⠂⡀⢳⡐⡪⢱⡌⠬⢙⡣⣨⣾⣿⣿
⣿⣿⣿⣿⣿⣿⡇⣺⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣕⣄⠈⠐⡙⠒⡀⡀⡀⡀⡀⡀⡀⣀⡤⡤⡤⣀⡀⢀⠁⡀⡀⢀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠂⡀⠨⡀⡀⢀⡀⡀⠁⡀⡀⡀⡀⠹⡅⡂⡰⢎⢱⢾⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠙⡀⠁⡀⠐⡀⡀⡀⢈⠙⠛⠉⠁⡀⡀⠉⠓⠦⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠂⡠⠪⢔⠊⡀⡀⡀⡀⡀⡀⡀⠹⢔⠊⣑⣼⡈⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⣾⣽⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢔⢅⢌⠅⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡗⣩⣶⣿⣧⢿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠠⠔⠒⠒⠒⠂⠅⠈⠁⡀⡀⠈⡀⠂⡀⡀⡀⡀⠂⡀⡀⡀⡀⢀⠴⠏⠅⢢⠎⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣘⣿⣿⣿⣿⠸⣿⣿⣿
*/