#include <bits/stdc++.h>
using namespace std;

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n; cin >> n;
        int mn = INT_MAX, mx = INT_MIN;

        for(int i = 0; i < n; ++i) {
            int x; cin >> x;
            mn = min(mn, x);
            mx = max(mx, x);
        }

        if(mn < 0) cout << mn << '\n';
        else cout << mx << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;
#define N 200010

int idx[N];

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n; cin >> n;

        for(int i = 1; i <= n; ++i) {
            int x; cin >> x;
            idx[x] = i;
        }

        if(idx[n] < min(idx[1], idx[2])) {
            cout << idx[n] << ' ' << min(idx[1], idx[2]) << '\n';
        } else if(idx[n] > max(idx[1], idx[2])) {
            cout << idx[n] << ' ' << max(idx[1], idx[2]) << '\n';
        } else {
            cout << idx[1] << ' ' << idx[2] << '\n';
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n, m; cin >> n >> m;

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(i % 2 == 0) cout << (n / 2 + i / 2) * m + j + 1 << ' ';
                else cout << (i / 2) * m + j + 1 << ' ';
            }
            cout << '\n';
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n, q; string s;
    cin >> n >> q >> s;

    set<int> a;

    for(int i = 1; i <= n; ++i)
        if((i % 2) != (s[i - 1] == '('))
            a.insert(i);

    while(q--) {
        int i; cin >> i;

        if(a.count(i)) a.erase(i);
        else a.insert(i);

        if(n % 2) cout << "NO\n";
        else if(a.size() && (*a.begin() % 2 || !(*a.rbegin() % 2))) cout << "NO\n";
        else cout << "YES\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll M = 1000000007;

ll pw(ll a, ll p) { return p ? pw(a * a % M, p / 2) * (p & 1 ? a : 1) % M : 1; }

ll inv(ll a) { return pw(a, M - 2); }

int main() {

    ll t; cin >> t;
    for(ll tc = 1; tc <= t; ++tc) {

        ll n, m, k, ai;
        cin >> n >> m >> k;
        for(ll i = 0; i < n; ++i) cin >> ai;

        ll ans = pw(k, m), mCi = 1;

        for(ll i = 0; i < n; ++i) {
            ans = (ans + M - mCi * pw(k - 1, m - i) % M) % M;
            mCi = mCi * (m - i) % M * inv(i + 1) % M;
        }

        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

char grid[110][110];
int n;
vector<pair<int, int>> snake;
map<pair<int, int>, char> getChar = {
    {{1, 0}, 'v'},
    {{-1, 0}, '^'},
    {{0, 1}, '>'},
    {{0, -1}, '<'}
};

pair<pair<int, int>, char> getBeltAndDir(pair<int, int> p) {
    if(p.first == -1) return {p, 'X'};
    pair<int, int> q = p;

    if(p.first == 0) q.first++;
    if(p.second == 0) q.second++;
    if(p.first > n) q.first--;
    if(p.second > n) q.second--;

    return {q, getChar[{p.first - q.first, p.second - q.second}]};
}

pair<pair<int, int>, char> query(int idx) {

    cout << "? " << snake[idx].first << ' ' << snake[idx].second << endl;

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j)
            cout << grid[i][j];
        cout << endl;
    }

    int i, j; cin >> i >> j;

    return getBeltAndDir({i, j});
}

void fillGrid() {
    for(int i = 0; i < n * n; ++i) {
        int dx = snake[i + 1].first - snake[i].first;
        int dy = snake[i + 1].second - snake[i].second;

        grid[snake[i].first][snake[i].second] = getChar[{dx, dy}];
    }
}

int main() {
    cin >> n;

    for(int i = 1; i <= n; ++i)
        if(i % 2 == 0)
            for(int j = n; j >= 1; --j)
                snake.emplace_back(i, j);
        else
            for(int j = 1; j <= n; ++j)
                snake.emplace_back(i, j);

    snake.emplace_back(n + 1, (n % 2 ? n : 1));
    fillGrid();

    auto ans = query(0);

    if(ans.second != 'X') {

        snake.pop_back();
        reverse(snake.begin(), snake.end());
        snake.emplace_back(0, 1);
        fillGrid();

        ans = query(0);
    }

    if(ans.second == 'X') {

        int id = 0;
        for(int j = 13; j >= 0; --j)
            if(id + (1 << j) < n * n && query(id + (1 << j)).second == 'X')
                id += (1 << j);

        ans.first = snake[id];

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(i < ans.first.first) grid[i][j] = '^';
                else if(i > ans.first.first) grid[i][j] = 'v';
                else grid[i][j] = j < ans.first.second ? '<' : '>';
            
        ans.second = query(id).second;
    }

    cout << "! " << ans.first.first << ' ' << ans.first.second << ' ' << ans.second << endl;
}

#include <bits/stdc++.h>
using namespace std;

int grid[45][45];

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n, m;
        cin >> n >> m;

        int max_i = 0, max_j = 0;
        
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> grid[i][j];
                if (grid[i][j] > grid[max_i][max_j])
                    max_i = i, max_j = j;
            }

        int h = max(max_i+1, n-max_i);
        int w = max(max_j+1, m-max_j);
        cout << h * w << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {

        int n; cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];

        if (n % 2 == 1) {
            cout << "Mike\n";
            continue;
        }

        int smallest = 0;
        for (int i = 0; i < n; ++i)
            if (a[i] < a[smallest])
                smallest = i;

        if (smallest % 2 == 0) cout << "Joe\n";
        else cout << "Mike\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 1010

int grid[N][N], mn[N][N], mx[N][N];

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n, m;
        cin >> n >> m;
        
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                cin >> grid[i][j];
        
        mn[0][0] = mx[0][0] = grid[0][0];
        
        for(int i = 1; i < n; ++i)
            mx[i][0] = mn[i][0] = mx[i - 1][0] + grid[i][0];
        
        for(int j = 1; j < m; ++j)
            mx[0][j] = mn[0][j] = mx[0][j - 1] + grid[0][j];
        
        for(int i = 1; i < n; ++i)
            for(int j = 1; j < m; ++j) {
                mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + grid[i][j];
                mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + grid[i][j];
            }
        
        if(mx[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 2010

vector<int> tree[N];

int dfs(int i, int p) {
    int sm = 0, z = 0;
    
    for (int j : tree[i]) if (j != p) {
        int x = dfs(j, i);
        sm += x;
        if (x == 0)
            z++;
    }
    
    return sm + max(0, z - 1);
}

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n;
        cin >> n;
        
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        
        if (n == 1)
            cout << "0\n";
        else {
            int ans = n;

            for (int i = 1; i <= n; ++i)
                ans = min(ans, 1 + dfs(i, i));
            
            cout << ans << '\n';
        }
        
        for (int i = 1; i <= n; ++i)
            tree[i].clear();
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 200010

vector<int> tree[N];

int dfs(int i, int p) {
    int sm = 0, z = 0;
    
    for (int j : tree[i]) if (j != p) {
        int x = dfs(j, i);
        sm += x;
        if (x == 0)
            z++;
    }
    
    return sm + max(0, z - 1);
}

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n;
        cin >> n;
        
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        int max_deg = 0;
        for (int i = 1; i <= n; ++i)
            max_deg = max(max_deg, (int)tree[i].size());
        
        if (max_deg == 0)
            cout << "0\n";
        else if (max_deg < 3)
            cout << "1\n";
        else {
            for (int i = 1; i <= n; ++i)
                if (tree[i].size() >= 3) {
                    cout << dfs(i, i) << '\n';
                    break;
                }
        }
        
        for (int i = 1; i <= n; ++i)
            tree[i].clear();
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 600010

vector<pair<int, int>> graph[N];
vector<int> lst;

int ans[2][N];

bool used[N], usedEdges[N];

void dfs(int i) {
    lst.push_back(i);

    if (!used[i]) {
        used[i] = true;
        
        for (pair<int, int> p : graph[i])
            if (!usedEdges[p.second]) {
                usedEdges[p.second] = true;
                dfs(p.first);
                lst.push_back(i);
            }
    }
}

int main() {

    int n; cin >> n;
    string ptop(n, 'U'), pbot(n, 'D');
    string mtop(n, 'U'), mbot(n, 'D');

    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v, i);
        graph[v].emplace_back(u, i);
    }

    int idx = 0;
    for (int i = 1; i <= 2 * n; ++i) if (!used[i]) {

        dfs(i);
        lst.pop_back();
        int k = lst.size() / 2;
        
        if (k == 1) {
            cout << "-1\n";
            exit(0);
        }

        for (int j = 0; j < k; ++j) {
            ans[0][j + idx] = lst[j];
            ans[1][j + idx] = lst[2 * k - 1 - j];
        }

        for (int j = 0; j < k - 1; j += 2)
            ptop[j + idx] = pbot[j + idx] = 'L', ptop[j + 1 + idx] = pbot[j + 1 + idx] = 'R';
        for (int j = 1; j < k - 1; j += 2)
            mtop[j + idx] = mbot[j + idx] = 'L', mtop[j + 1 + idx] = mbot[j + 1 + idx] = 'R';
        lst.clear();

        idx += k;
    }

    cout << "2 " << n << '\n';
    
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < n; ++j)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }

    cout << ptop << '\n' << pbot << '\n';
    cout << mtop << '\n' << mbot << '\n';
}