#include <bits/stdc++.h>
 
using namespace std;
 
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        auto get = [&](int x, int y) {
            if (x >= 0 && x < n && y >= 0 && y < n) return x * n + y + 1;
            return 0;
        };
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int cur = get(i, j);
                for (int d = 0; d < 4; ++d) cur += get(i + dx[d], j + dy[d]);
                ans = max(ans, cur);
            }
        }
        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 1;
    if (n == 2) ans = 9;
    else if (n == 3 || n == 4) ans = 4 * n * n - n - 4;
    else if (n > 4) ans = 5 * n * n - 5 * n - 5;
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
 
    int sum = 0;
    int cnt_one = 0;
 
    for (int i = 0; i < n; i++){
        if (a[i] > 0){
            cnt_one++;
        }
        sum += a[i];
    }
 
    int sum2 = sum - cnt_one;
    int sub = n - 1 - sum2;
 
    cout << cnt_one - max(0ll, sub) << '\n';
}
 
signed main()
{
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
#ifdef FELIX
    cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
        chrono::high_resolution_clock::now()
            - _clock_start).count() << "ms." << endl;
#endif
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
 
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
inline void solve() {
    int n; li k;
    cin >> n >> k;
    vector<int> q(n), r(n);
    fore (i, 0, n)
        cin >> q[i];
    fore (i, 0, n)
        cin >> r[i];
    
    sort(q.begin(), q.end());
    sort(r.begin(), r.end());
 
    auto check = [&](int cnt) {
        fore (i, 0, cnt) {
            if (li(q[i] + 1) * (r[cnt - 1 - i] + 1) - 1 > k)
                return false;
        }
        return true;
    };
 
    int lf = 0, rg = n + 1;
    while (rg - lf > 1) {
        int mid = (lf + rg) >> 1;
        if (check(mid))
            lf = mid;
        else
            rg = mid;
    }
    cout << lf << endl;
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int t = 1; cin >> t;
    while (t--) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int cost(char c)
{
    if(c == 'I') return 1;
    return 5;
}

int eval(string s)
{
    int n = s.size();
    int ans = 0;
    for(int i = 0; i < n; i++)
        if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V')
            ans--;
        else ans += cost(s[i]);
    return ans;    
}

void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'X')
        {
            s[i] = 'V';
            ans += 5;
        }
    }
    int inc = 0;
    int same = 0;
    int qcount = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] != '?') continue;
        int r = i;
        while(r < n && s[r] == '?') r++;
        int len = r - i;
        if(i > 0 && s[i - 1] == 'I') len++;
        if(r < n && s[r] == 'V') 
        {
            inc--;
            len++;
        }
        inc += len / 2;
        same += len % 2;
        qcount += (r - i);
        i = r - 1;        
    }
    for(int i = 0; i < n; i++)
        if(s[i] == '?') s[i] = 'I';
    ans += eval(s);
    for(int i = 0; i < q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int used_v = max(0, min(b, qcount - c));
        int used_x = max(0, qcount - c - b);
        int cur = ans;
        cur += used_v * 4 + used_x * 9;
        int rep = used_v + used_x;
        cur -= min(inc, rep) * 2;
        rep -= (inc + same);
        cur += max(0, rep) * 2;
        cout << cur << "\n";  
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9;
const int MOD = 998244353;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> max_left(n + 1, -1);
    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        max_left[r] = max(max_left[r], l);
    }
    for(int i = 1; i <= n; i++)
        max_left[i] = max(max_left[i], max_left[i - 1]);
    vector<int> dp(n + 1);
    vector<int> prefsum(n + 2);
    dp[0] = 2;
    prefsum[1] = 2;
    for(int i = 1; i <= n; i++)
    {
        int j = max_left[i - 1] + 1;
        dp[i] = add(prefsum[i], -prefsum[j]);
        prefsum[i + 1] = add(prefsum[i], dp[i]);
    }
    cout << dp[n] << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int B = 13;
const int M = (1 << (B - 1));
const int INF = 1e9;
 
int dp[B][M];
 
void upd(int& a, int b)
{
    if(a < b) a = b;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> id(n);
    int q;
    cin >> q;
    vector<int> l(q), x(q);
    for(int i = 0; i < q; i++)
    {
        int r;
        cin >> l[i] >> r >> x[i];
        --l[i];
        --r;
        id[r].push_back(i);
    }
    
    for(int i = 0; i < B; i++)
        for(int j = 0; j < M; j++)
            dp[i][j] = -INF;
    dp[0][0] = INF;
    vector<int> ans(q, 0);
    for(int i = 0; i < n; i++)
    {
        int val = a[i];
        upd(dp[1][val], i);
        for(int j = 1; j < B - 1; j++)
        {
            for(int k = 1; k < M; k++)
            {
                upd(dp[j + 1][k ^ val], dp[j][k]);
            }
        }
        for(auto qr : id[i])
        {
            int cur = x[qr];
            for(int j = B - 1; j >= 0; j--)
                if(dp[j][cur] >= l[qr])
                    ans[qr] = j;
        }
    }
    
    for(int i = 0; i < q; i++)
        cout << ans[i] << " ";
    cout << endl;
}