Mahesh có một mảng tuyệt đẹp tên A làm quà sinh nhật từ cô bạn gái xinh đẹp Nam-ra-tha. Có N số nguyên dương trong mảng đó. Mahesh yêu thích mảng này đến mức anh bắt đầu dành nhiều thời gian cho nó hàng ngày. Một ngày nọ, anh viết ra tất cả các tập con có thể có của mảng. Sau đó, với mỗi tập hợp con, anh ta tính tổng các phần tử trong tập hợp con đó và viết nó xuống một tờ giấy. Thật không may, Mahesh đã mất mảng đẹp đó. Anh ấy vẫn còn tờ giấy mà đã viết tất cả các tập hợp con.

Nhiệm vụ của bạn là xây dựng lại mảng A đẹp giúp cặp đôi hạnh phúc này nhé.

Input:

• Dòng đầu tiên chứa số nguyên dương 𝑇 (𝑇 ≤ 50) là số bộ dữ liệu.

• Tiếp theo là T nhóm dòng, mỗi nhóm dòng mô tả một bộ dữ liệu với cấu trúc:

• Dòng đầu tiên chứa số nguyên dương (1 ≤ 𝑁 ≤ 15)

• Dòng thứ hai chứa 2^𝑁 số nguyên là tổng của các tập con mà Nam ghi được.

Các số nguyên này có giá trị không vượt quá 10^9.

Ouptut:

Với mỗi bộ dữ liệu in ra trên một dòng số tìm được theo giá trị không giảm

Sample Input

2
1
0 10
2
0 1 1 2

Sample Output

10
1