Hùng quan sát một kim tự tháp N tầng, đánh số từ 1 đến N, từ đáy lên đỉnh. Tầng thứ i được ghép bởi 2 ∗ i − 1 khối gạch đơn vị hình vuông xếp liên tiếp nhau thành hàng ngang. Kim tự tháp được xây dựng sao cho các khối gạch ở trung tâm của các tầng thẳng hàng với nhau theo chiều dọc.

Hùng viết 2 ∗ N − 1 số nguyên A1, A2, . . . , AN vào các khối gạch của tầng N. Sau đó, anh ta viết các số nguyên vào tất cả các khối còn lại, theo quy tắc sau: Số nguyên được viết vào khối gạch b phải bằng trung vị của ba số nguyên ở ba khối trực tiếp dưới b, hoặc ở phía dưới ngay bên trái hoặc phía dưới ngay bên phải của b.

Sau đó, anh ta xóa tất cả các số nguyên được viết trong các khối và chỉ nhớ 2N − 1 số được ghi ở tầng N.

Yêu cầu: Hãy tìm lại giá trị số nguyên đã được Hùng ghi trên khổi gạch tầng 1 của kim tự tháp.

Dữ liệu vào

Dòng đầu chứa một số nguyên dương T (T ≤ 1000) là số lượng bộ test.

Mỗi dòng trong số T nhóm dòng sau gồm:

– dòng đầu chứa một số nguyên dương N (N ≤ 10^5);

– dòng thứ hai chứa 2N − 1 số nguyên không âm A1, A2, . . . , AN (Ai ≤ 10^9).

Kết quả

Ghi ra T dòng, mỗi dòng là kết quả tìm được của bộ test tương ứng trong input.

Sample Input

2
4
1 6 3 7 4 5 2
5
1 2 3 7 8 9 6 4 5

Sample Output

4
8

Hạn chế

Trong mọi bộ test, tổng tất cả các giá trị N không quá 5 × 10^5;
ˆ Subtask 1: 30% số điểm có tổng mọi giá trị N trong mọi bộ test không quá 5000;
ˆ Subtask 2: 30% số điểm khác có Ai ∈ [0, 1] với mọi i ∈ [1, 2N − 1] trong mọi bộ test;
ˆ Subtask 3: 40% số điểm còn lại không có giới hạn gì thêm.