Cho một dãy số nguyên không âm ~A~ gồm ~N~ phần tử. Với các toán tử trên bit, hãy tính:

$$\sum_{1 \le i \le j \le N} \big((A_i \text{ or } A_j) \text{ xor } (A_j \text{ and } A_i)\big)$$

Dữ liệu

• Dòng đầu tiên chứa số nguyên duy nhất ~T~ là số test ~(T \le 10)~.

• Dòng đầu tiên của mỗi test, chứa một số nguyên duy nhất ~N~ ~(N \le 10^5)~.

• Dòng thứ hai của mỗi test, chứa ~N~ số nguyên không âm, số thứ ~i~ là phần tử ~A_i~ ~(A_i < 2^{31})~.

Kết quả

• Với mỗi test, in kết quả trên một dòng gồm số nguyên duy nhất của bài toán.

Ví dụ

Sample Input

2
2
1 3
3
7 1 3

Sample Output

2
12

Chấm điểm

• Subtask 1 (50% số test): ~1 \le N \le 10^3~.

• Subtask 2 (50% số test): Không có ràng buộc gì thêm.