#include <random>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
 
using namespace std;
 
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define pii pair<int, int>
#define pb emplace_back
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &c : a) cin >> c;
        int mx = 0;
        for (int i = 0; i < n - 1; i++) mx = max(mx, a[i]);
        cout << mx + a[n - 1] << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, a, b;
        cin >> n >> a >> b;
        if (b <= a) {
            cout << n * a << endl;
        } else {
            long long k = min(b &mdash; a + 1, n);
            cout << (b &mdash; k + 1) * n + k * (k &mdash; 1) / 2 << endl;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        int n;
        ll k;
        cin >> n >> k;
        ll max_s = 0;
        for (int i = 0; i < n; i++) max_s += abs(n &mdash; 1 &mdash; i &mdash; i);
        if (k % 2 != 0 || k > max_s) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
            vector<int> p(n);
            k /= 2;
            iota(p.begin(), p.end(), 0);
            for (int i = 0; k > 0; i++) {
                if (k >= n &mdash; 1 &mdash; 2 * i) {
                    swap(p[i], p[n &mdash; 1 &mdash; i]);
                    k -= n &mdash; 1 &mdash; 2 * i;
                } else {
                    swap(p[i], p[i + k]);
                    k = 0;
                }
            }
            for (int i = 0; i < n; i++) {
                cout << p[i] + 1 << " ";
            }
            cout << "\n";
        }
    }
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n, c;
    cin >> n >> c;

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

    if (n == 1) {
        cout << "0\n";
        return;
    }

    int mx = *max_element(a.begin() + 1, a.end());
    int mxc = max(a[0] + c, mx);
    int winner = mxc == a[0] + c ? 0 : find(a.begin() + 1, a.end(), mx) - a.begin();
    ll sum = c;
    for (int i = 0; i < n; sum += a[i], ++i) {
        int answer;
        if (i == winner) {
            answer = 0;
        } else if (sum + a[i] >= mx) {
            answer = i;
        } else {
            answer = i + 1;
        }
        cout << answer << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test = 1;
    cin >> test;
    
    while (test--) {
        solve();
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    string s, t;
    cin >> n >> s >> t;
    auto get_range = [&] (int i) {
      if (s[i] == '1') return make_pair(i, i);
      int l = -1, r = -1;
      if (i > 0 && t[i-1] == '1') l = i-1;
      else if (i > 1 && t[i-1] == '0' && s[i-2] == '0') l = i-2;
      if (i+1 < n && t[i+1] == '1') r = i+1;
      else if (i+2 < n && t[i+1] == '0' && s[i+2] == '0') r = i+2;
      if (l == -1) r = -1;
      if (r == -1) l = -1;
      return make_pair(l, r);
    };
 
    vector<int> pref(n+1);
    for (int i = 0; i < n; i++) pref[i+1] = pref[i] + (get_range(i).first != -1);
 
    int q;
    cin >> q;
    while (q--) {
      int l, r;
      cin >> l >> r;
      int ans = 0;
      if (r-l <= 5) {
        for (int i = l-1; i < r; i++) {
          auto [ll, rr] = get_range(i);
          if (ll >= l-1 && rr < r) ans++;
        }
      }
      else {
        ans = pref[r] - pref[l-1];
        for (int j: {l-1, l, r-2, r-1}) {
          auto [ll, rr] = get_range(j);
          if (ll != -1 && (ll < l-1 || rr >= r)) ans--;
        }
      }
      cout << ans << '\n';
    }
  }
}

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
 
using namespace std;
 
using ll = long long;
 
const int MAXA = 1e6;
 
int n, k;
vector<int> a;
vector<int> primes_x[MAXA + 1];
unordered_map<int, int> last_ind_p;
vector<bool> is_prime(MAXA + 1, true);
vector<int> primes;
 
void read() {
	cin >> n >> k;
	a.assign(n, 0);
	for (int& elem : a) {
		cin >> elem;
	}
}
 
vector<int> p, sz, p_rs;
 
int col(int A) {
	return (A == p[A] ? A : p[A] = col(p[A]));
}
 
void unique(int A, int B) {
	A = col(A); B = col(B);
	if (A == B) return;
	if (sz[A] < sz[B]) {
		swap(A, B);
	}
	p[B] = A;
	sz[A] += sz[B];
}
 
void solve() {
    last_ind_p.clear();
	vector<int> aa;
	for (int i = 1; i < n; i++) {
		aa.push_back(a[i]);
	}
	for (int i = 0; i < n; i++) {
		aa.push_back(a[i]);
	}
	a = aa;
	int n2 = n;
	n = a.size();
	p.assign(n, -1);
	p_rs.assign(n, -1);
	sz.assign(n, -1);
	for (int i = 0; i < n; i++) {
		p[i] = i;
		sz[i] = 1;
	}
 
	for (int i = 0; i < n2; i++) {
		p_rs[i] = i + 1;
		p_rs[2 * n2 - 2 - i] = i + 1;
	}
	vector<int> a2 = a;
	sort(a2.begin(), a2.end());
	a2.resize(unique(a2.begin(), a2.end()) - a2.begin());
    unordered_set<int> to_clean;
	for (int elem : a2) {
		int cur_elem = elem;
		for (ll p : primes) {
			if (p * p > elem) break;
			if (elem % p == 0) {
				primes_x[cur_elem].push_back(p);
                if (primes_x[cur_elem].size() == 1) {
                    to_clean.insert(cur_elem);
                }
			}
			while (elem % p == 0) {
				elem /= p;
			}
		}
		if (elem > 1) {
			primes_x[cur_elem].push_back(elem);
            if (primes_x[cur_elem].size() == 1) {
                to_clean.insert(cur_elem);
            }
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int cur_p : primes_x[a[i]]) {
			if (last_ind_p.count(cur_p) && i - last_ind_p[cur_p] <= k) {
				unique(last_ind_p[cur_p], i);
			}
			last_ind_p[cur_p] = i;
		}
	}
    for (int i : to_clean)
        primes_x[i].clear();
}
 
void write() {
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (p[i] == i) {
			if (a[i] > 1) {
				ans += 1;
			}
			else {
				ans += p_rs[i];
			}
		}
	}
	cout << ans << endl;
}
 
int main() {
    for (ll i = 2; i <= MAXA; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= MAXA; j += i) {
                is_prime[j] = false;
            }
        }
    }
	ios_base::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        read();
        solve();
        write();
    }
}