Min Or Sum solution codeforces

Min Or Sum solution codeforces

 

You are given an array aa of size nn.

You can perform the following operation on the array:

  • Choose two different integers i,ji,j (1i<jn(1≤i<j≤n), replace aiai with xx and ajaj with yy. In order not to break the array, ai|aj=x|yai|aj=x|y must be held, where || denotes the bitwise OR operation. Notice that xx and yy are non-negative integers.

Please output the minimum sum of the array you can get after using the operation above any number of times.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1000)(1≤t≤1000). Description of the test cases follows.

The first line of each test case contains an integer nn (2n100)(2≤n≤100) — the size of array aa.

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (0ai<230)(0≤ai<230).

Output

For each test case, print one number in a line — the minimum possible sum of the array.

Example
input

Copy
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
output

Copy
3
31
6
7
Note

In the first example, you can perform the following operations to obtain the array [1,0,2][1,0,2]:

1. choose i=1,j=2i=1,j=2, change a1=1a1=1 and a2=2a2=2, it’s valid since 1|3=1|21|3=1|2. The array becomes [1,2,2][1,2,2].

2. choose i=2,j=3i=2,j=3, change a2=0a2=0 and a3=2a3=2, it’s valid since 2|2=0|22|2=0|2. The array becomes [1,0,2][1,0,2].

We can prove that the minimum sum is 1+0+2=31+0+2=3

In the second example, We don’t need any operations.

Leave a Comment

Your email address will not be published.