Tirth and Souvik play Badminton a lot. Everytime they play with each other, Souvik wins. Tirth doesn't like losing. So he comes up with his own rule.

Tirth gives Souvik an array of size n. Souvik will win if he is able to score equal to the number of distinct Magic numbers of all possible contiguous subarrays of the given array. So Souvik needs to find the total points he has to score to win.

Magic number of an array is the bitwise and of all elements.

Input

First line contains the number of test cases t. The description of t test cases follows.

First line of each test case contains a single integer n denoting the size of the array.

The second line contains n space-separated integers representing elements of the array.

Output

For each testcase, print a single line containing the required output.

Constraints

1 <= t <= 3
1 <= n <= 10^5
0 <= A[i] <= 10^6

40% score :
1 <= n <= 1000

100% score :
Original constraints