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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		set<int> s;
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			s.insert(x);
		}
		cout << s.size() * 2 - 1 << '\n';
	}
}

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

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

	int t;
	cin >> t;
	while (t--)
	{
		int n, ra, ca, rb, cb;
		cin >> n >> ra >> ca >> rb >> cb;
		int ans = 0;
		if (rb > ra)
			ans = max(ans, rb);
		else if (rb < ra)
			ans = max(ans, n - rb);
		if (cb > ca)
			ans = max(ans, cb);
		else if (cb < ca)
			ans = max(ans, n - cb);
		cout << ans << '\n';
	}
}

/*
* T1 Thanks Round
* Problem triple-removal
* Main Correct Solution
*/

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

const int MAX = 250'010;

int A[MAX];

int diff[MAX];
int diffsum[MAX];

int sum[2][MAX];

void solve() {
	int N, Q;
	cin >> N >> Q;
	int i;
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) {
		sum[0][i] = sum[0][i - 1];
		sum[1][i] = sum[1][i - 1];
		sum[A[i]][i]++;

		diff[i] = A[i] != A[i - 1];
		diffsum[i] = diffsum[i - 1] + diff[i];
	}
	int l, r;
	for (i = 1; i <= Q; i++) {
		cin >> l >> r;

		int z, o;
		z = sum[0][r] - sum[0][l - 1];
		o = sum[1][r] - sum[1][l - 1];
		if (z % 3) {
			cout << -1 << '\n';
			continue;
		}
		if (o % 3) {
			cout << -1 << '\n';
			continue;
		}

		int sum = z / 3 + o / 3;
		if (diffsum[r] - diffsum[l] == (r - l)) sum++;
		cout << sum << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int t, T;
	cin >> T;
	for (t = 1; t <= T; t++) solve();
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAXN = 250000;

int a[MAXN + 100];
ll prf[MAXN + 100][4];

void solve(){
    int n, q;
    scanf("%d %d", &n, &q);

    for (int i=1;i<=n;i++) scanf("%d", a+i);
    
    for (int i=1;i<=n;i++){
        for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j];
        
        int typ = 2;
        if (popcount((unsigned)a[i]) == 1) typ = 0;
        else if (popcount((unsigned)a[i]-1) == 1) typ = 1;

        prf[i][typ]++;

        prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i]));
    }

    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);

        ll cnt[3] = {0};
        for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j];

        ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2;
        printf("%lld\n", ans);
    }
}

int main(){
    int t;
    scanf("%d", &t);

    while(t--) solve();
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

void solve() {
	int n;
	cin >> n;
	vector<int> ord(n * n + 1);
	iota(all(ord), 0);
	auto query = [&](vector<int> v) {
		cout << "? " << sz(v);
		for (auto &x : v)
			cout << " " << x + 1;
		cout << endl;
		int y;
		cin >> y;
		v.resize(y);
		for (auto &x : v)
			cin >> x, x--;
		return v;
	};
	vector<int> dp(n * n + 1, n);
	for (int i = 0; i < n; i++) {
		auto cur_ord = query(ord);
		if (sz(cur_ord) > n) {
			cout << "!";
			for (int i = 0; i < n+1; i++)
				cout << " " << cur_ord[i] + 1;
			cout << endl;
			return;
		}
		vector<int> new_ord;
		for (auto &x : ord) {
			if (!binary_search(all(cur_ord), x)) {
				new_ord.push_back(x);
			} else dp[x] = i;
		}
		ord = new_ord;
	}
	int cur = n;
	vector<int> ans;
	for (int i = n * n; i >= 0; i--) {
		if (dp[i] == cur) {
			ans.push_back(i);
			cur--;
		}
	}
	if(sz(ans) != n + 1){
	    cerr << cur << endl;
	    for(auto &x : dp) cerr << x << " ";
	    cerr << endl;
	}
	reverse(all(ans));
	assert(sz(ans) == n+1);
	cout << "!";
	for (auto &x : ans)
		cout << " " << x + 1;
	cout << endl;
}

int main() {
	int tc;
	cin >> tc;
	while (tc--)
		solve();
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
const int MAXN = 500005;

int nxt1[20][MAXN], dep1[MAXN];
pi nxt2[20][MAXN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	
	while (T--){
    	int n, t;
    	cin >> n >> t;
    	t++;
    	vector<int> a(n);
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    	
    	// EDIT: added init statements for globals
    	for (int i = 0; i < n+5; i++){
    	    for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0};
    	    dep1[i]=0;
    	}
    		
    	int j = 0;
    	for (int i = 0; i < n; i++) {
    		while (j < n && a[j] < a[i] + t)
    			j++;
    		nxt1[0][i] = j;
    	}
    	nxt1[0][n] = n;
    	for (int i = n - 1; i >= 0; i--)
    		dep1[i] = dep1[nxt1[0][i]] + 1;
    	for (int i = 1; i < 20; i++) {
    		for (int j = 0; j <= n; j++)
    			nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]];
    	}
    	auto lca = [&](int u, int v) {
    		if (dep1[u] > dep1[v])
    			swap(u, v);
    		int dx = dep1[v] - dep1[u];
    		for (int i = 0; dx; i++) {
    			if (dx & 1) {
    				v = nxt1[i][v];
    			}
    			dx >>= 1;
    		}
    		if (u == v)
    			return u;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt1[i][u] != nxt1[i][v]) {
    				u = nxt1[i][u];
    				v = nxt1[i][v];
    			}
    		}
    		return nxt1[0][u];
    	};
    	for (int i = 0; i < n; i++) {
    		int z = lca(i, i + 1);
    		nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]};
    	}
    	nxt2[0][n] = pi{n, 0};
    	for (int i = 1; i < 20; i++) {
    		for (int j = 0; j <= n; j++) {
    			auto [n1, d1] = nxt2[i - 1][j];
    			auto [n2, d2] = nxt2[i - 1][n1];
    			nxt2[i][j] = pi{n2, d1 + d2};
    		}
    	}
    	auto gp = [&](int l, int r) {
    		int ans = 0;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt1[i][l] < r) {
    				l = nxt1[i][l];
    				ans += (1 << i);
    			}
    		}
    		return ans + 1;
    	};
    	int q;
    	cin >> q;
    	while (q--) {
    		int l, r;
    		cin >> l >> r;
    		l--;
    		if (r - l <= 2) {
    			cout << r - l << "\n";
    			continue;
    		}
    		int ans = 0;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt2[i][l][0] < r) {
    				ans += nxt2[i][l][1];
    				l = nxt2[i][l][0];
    			}
    		}
    		if (l + 1 <= r)
    			ans += gp(l, r);
    		if (l + 2 <= r)
    			ans += gp(l + 1, r);
    		cout << ans << "\n";
    	}
	}
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 250005;
const int MAXT = 1050000;

struct mtrx {
	int nxt[2];
	mtrx() { nxt[0] = nxt[1] = 0; }
	mtrx(int x) {
		nxt[x] = 1;
		nxt[1 ^ x] = 0;
	}
	mtrx operator+(const mtrx &m) const {
		mtrx ret;
		ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2];
		ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2];
		return ret;
	}
};

struct node {
	mtrx M[2];
	int lazy;
	node operator+(const node &nd) const {
		node ret;
		ret.M[0] = M[0] + nd.M[0];
		ret.M[1] = M[1] + nd.M[1];
		ret.lazy = 0;
		return ret;
	}
} tree[MAXT];

void init(int s, int e, int p, vector<pi> &seq) {
	if (s == e) {
		tree[p].M[seq[s][0]] = mtrx(seq[s][1]);
		tree[p].M[1 ^ seq[s][0]] = mtrx();
		return;
	}
	int m = (s + e) / 2;
	init(s, m, 2 * p, seq);
	init(m + 1, e, 2 * p + 1, seq);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

void lazydown(int p) {
	if (tree[p].lazy) {
		for (int i = 2 * p; i < 2 * p + 2; i++) {
			tree[i].lazy ^= 1;
			swap(tree[i].M[0], tree[i].M[1]);
		}
		tree[p].lazy = 0;
	}
}

void update(int s, int e, int ps, int pe, int p) {
	if (e < ps || pe < s)
		return;
	if (s <= ps && pe <= e) {
		tree[p].lazy ^= 1;
		swap(tree[p].M[0], tree[p].M[1]);
		return;
	}
	int pm = (ps + pe) / 2;
	lazydown(p);
	update(s, e, ps, pm, 2 * p);
	update(s, e, pm + 1, pe, 2 * p + 1);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

int query() { return tree[1].M[1].nxt[0] / 2; }

vector<int> gph[MAXN];
int a[MAXN], din[MAXN], dout[MAXN];
vector<pi> seq;

void dfs(int x, int p = -1) {
	din[x] = sz(seq);
	seq.push_back({a[x], 0});
	for (auto &y : gph[x]) {
		if (y != p)
			dfs(y, x);
	}
	seq.push_back({a[x], 1});
	dout[x] = sz(seq);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin >> T;
	while (T--) {
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    		
    	for (int i = 0; i < n; i++) gph[i].clear();
    	seq.clear();
    	
    	for (int i = 0; i < n - 1; i++) {
    		int u, v;
    		cin >> u >> v;
    		u--;
    		v--;
    		gph[u].push_back(v);
    		gph[v].push_back(u);
    	}
    	dfs(0);
    	init(0, sz(seq) - 1, 1, seq);
    	cout << query() << "\n";
    	int q;
    	cin >> q;
    	while (q--) {
    		int v;
    		cin >> v;
    		v--;
    		update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1);
    		cout << query() << "\n";
    	}
	}
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

vector<int> pa;

int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin>>T;
	while (T--){
		int n;
		cin >> n;
		vector<array<lint, 3>> edges;
		for (int i = 0; i < n - 1; i++) {
			lint u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;
			edges.push_back({w, u, v});
		}
		sort(all(edges));
		reverse(all(edges));
		cr(pa, 2 * n - 1);
		vector<lint> cost(2 * n - 1);
		vector<pi> ch(2 * n - 1);
		iota(all(pa), 0);
		for (int i = 0; i < n - 1; i++) {
			int u = find(edges[i][1]);
			int v = find(edges[i][2]);
			pa[u] = i + n;
			pa[v] = i + n;
			ch[i + n] = {u, v};
			cost[edges[i][1]] += edges[i][0];
			cost[edges[i][2]] += edges[i][0];
			cost[i + n] -= edges[i][0] * 2;
		}
		for (int i = n; i < 2 * n - 1; i++) {
			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
		}
		int q;
		cin >> q;
		while (q--) {
			lint x;
			cin >> x;
			vector<lint> dp(2 * n - 1);
			lint dap = 0;
			for (int i = 0; i < 2 * n - 1; i++) {
				if (i >= n) {
					dp[i] += dp[ch[i][0]] + dp[ch[i][1]];
				}
				if (dp[i] + cost[i] < x) {
					dap += x - cost[i] - dp[i];
					dp[i] = x - cost[i];
				}
			}
			cout << dap << "\n";
		}
	}
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

vector<int> pa;

int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin>>T;
	while (T--){
		int n;
		cin >> n;
		vector<array<lint, 3>> edges;
		for (int i = 0; i < n - 1; i++) {
			lint u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;
			edges.push_back({w, u, v});
		}
		sort(all(edges));
		reverse(all(edges));
		cr(pa, 2 * n - 1);
		vector<lint> cost(2 * n - 1);
		vector<pi> ch(2 * n - 1);
		iota(all(pa), 0);
		for (int i = 0; i < n - 1; i++) {
			int u = find(edges[i][1]);
			int v = find(edges[i][2]);
			pa[u] = i + n;
			pa[v] = i + n;
			ch[i + n] = {u, v};
			cost[edges[i][1]] += edges[i][0];
			cost[edges[i][2]] += edges[i][0];
			cost[i + n] -= edges[i][0] * 2;
		}
		for (int i = n; i < 2 * n - 1; i++) {
			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
		}
		// (point, slope increase)
		vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n);
		vector<int> idx(2 * n - 1);
		iota(all(idx), 0);
		for (int i = 0; i < 2 * n - 1; i++) {
			if (i < n) {
				pq[i].push({cost[i], 1});
				continue;
			}
			if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]]))
				swap(ch[i][0], ch[i][1]);
			idx[i] = idx[ch[i][0]];
			while (sz(pq[idx[ch[i][1]]])) {
				auto tp = pq[idx[ch[i][1]]].top();
				pq[idx[ch[i][1]]].pop();
				pq[idx[i]].push(tp);
			}
			if (cost[i] >= pq[idx[i]].top()[0])
				continue;
			if (cost[i] >= lint(2e9))
				continue;
			lint A = 0, B = 0;
			lint pv = -1;
			while (sz(pq[idx[i]])) {
				auto [point, slope] = pq[idx[i]].top();
				pq[idx[i]].pop();
				B += A * (point - pv);
				pv = point;
				A += slope;
				// A x - A * pv + B = x - cost[i]
				// (A - 1) x = A * pv - B - cost[i]
				lint U = A * pv - B - cost[i];
				lint L = A - 1;
				// point <= U / L, so no need to dedup
				if (L > 0) {
					assert(point * L <= U);
					if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) {
						lint f1 = U / L - cost[i];
						lint f2 = (U / L + 1 - pv) * A + B;
						// (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A
						pq[idx[i]].push({cost[i], 1});
						pq[idx[i]].push({U / L, f2 - f1 - 1});
						pq[idx[i]].push({U / L + 1, A - (f2 - f1)});
						break;
					}
				} else if (sz(pq[idx[i]]) == 0) {
					pq[idx[i]].push({cost[i], 1});
					break;
				}
			}
		}
		int q;
		cin >> q;
		vector<pi> queries(q);
		for (int i = 0; i < q; i++) {
			cin >> queries[i][0];
			queries[i][1] = i;
		}
		sort(all(queries));
		vector<lint> ans(q);
		lint A = 0, B = 0, pv = -1;
		auto T = idx[2 * n - 2];
		for (auto &[x, i] : queries) {
			while (sz(pq[T]) && pq[T].top()[0] <= x) {
				auto [point, slope] = pq[T].top();
				pq[T].pop();
				B += A * (point - pv);
				pv = point;
				A += slope;
			}
			ans[i] = (x - pv) * A + B;
		}
		for (auto &v : ans)
			cout << v << "\n";
	}
}