Chang and Bitwise OR

Chang and Bitwise OR 

Chang is a big fan of bitwise operations. As he was sitting in a boring lecture, he thought of a simple problem but had a tough time figuring out the solution. Help him to solve it. The problem is as follows.

Given a list of N non-negative integers, you perform the following operation on this list. Select any subsequence of integers from the list and remove the elements of that subsequence. The cost incurred will be Bitwise OR of the elements. 
Your task is to remove all the integers from the list by applying the above operation as many times as you want. You want to incur the minimum total cost at the end. Total cost is the sum of all the costs incurred while removing subsequences.

Input

The first line of the input contains an integer T denoting the number of test cases.

The first line of the each test case contains a single integer N denoting the number of integers in the list.

The second line contains N space-separated integers A1, A2, ..., AN denoting the integers in the given list.

Output

For each test case, output answer in a separate line.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 105

0 ≤ Ai ≤ 109

Example

Input:

1
2
1 2

Output:

3

Solution:

#include <stdio.h>
#define gc getchar_unlocked
int rin() {
 char c = gc(); 
while(c<'0' || c>'9')
 c = gc();
 int ret = 0; 
while(c>='0' && c<='9')
 { 
ret = 10 * ret + c - 48; 
c = gc();
 } 
return ret;
 }
long long int rinl()
 { 
char c = gc();
 while(c<'0' || c>'9')
 c = gc();
 long long int ret = 0; 
while(c>='0' && c<='9') {
 ret = 10 * ret + c - 48; 
c = gc();
 } 
return ret;
 }
int main() {
     int T = rin(), n, ans, i, t;
     while(T--)
    {
      n = rin();
      ans = 0;
      for(i = 0;i<n;i++) 
      t = rin(), ans |= t;
      printf("%d\n", ans);
    }
    return 0;
  }