#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define For(i,s,a) for(lld i = (lld)s; i < (lld)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define sz size()
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ZAPS {int t; scanf("%i", &t); while(t--) solve();}
#define nieZAPS solve();
#define make_unique(x) (x).erase( unique(all(x)), (x).end())
 
 
template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

const int N = 5e5 + 1;

lld c[N];
lld at_least[61];
lld mod = 1e9 + 7;
lld potega[61];

void solve(void){
	memset(at_least, 0, sizeof(at_least));
	int n;
	scanf("%i", &n);
	For(i, 0, n)
		scanf("%lli", &c[i]);
	For(i, 0, n){
		For(j, 0, 61)
			if((1ll << j) & c[i])
				++at_least[j];
	}
	lld wyn = 0;
		
		
	For(i, 0, n){
		lld ory = 0;
		For(j, 0, 61)
			if((1ll << j) & c[i])
				ory = (ory + potega[j] * (lld)n) % mod;
			else
				ory = (ory + potega[j] * at_least[j]) % mod;
		lld andy = 0;
		For(j, 0, 61)
			if((1ll << j) & c[i])
				andy = (andy + potega[j] * at_least[j]) % mod;
		wyn = (wyn + ory * andy) % mod;
	}	
	printf("%lli\n", wyn);
}

int32_t main(void){
	
	For(i, 0, 61)
		potega[i] = (1ll << i) % mod;
	ZAPS
}

/*
0?1
2 3
*/

### Prompt

Your challenge is to write a CPP solution to the following problem:

Only a few know that Pan and Apollo weren't only battling for the title of the GOAT musician. A few millenniums later, they also challenged each other in math (or rather in fast calculations). The task they got to solve is the following:

Let x_1, x_2, …, x_n be the sequence of n non-negative integers. Find this value: $$$∑_{i=1}^n ∑_{j=1}^n ∑_{k=1}^n (x_i   \&   x_j) ⋅ (x_j   |   x_k)$$$

Here \& denotes the [bitwise and,](https://en.wikipedia.org/wiki/Bitwise_operation#AND) and | denotes the [bitwise or.](https://en.wikipedia.org/wiki/Bitwise_operation#OR)

Pan and Apollo could solve this in a few seconds. Can you do it too? For convenience, find the answer modulo 10^9 + 7.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 1 000) denoting the number of test cases, then t test cases follow.

The first line of each test case consists of a single integer n (1 ≤ n ≤ 5 ⋅ 10^5), the length of the sequence. The second one contains n non-negative integers x_1, x_2, …, x_n (0 ≤ x_i < 2^{60}), elements of the sequence.

The sum of n over all test cases will not exceed 5 ⋅ 10^5.

Output

Print t lines. The i-th line should contain the answer to the i-th text case.

Example

Input


8
2
1 7
3
1 2 4
4
5 5 5 5
5
6 2 2 1 0
1
0
1
1
6
1 12 123 1234 12345 123456
5
536870912 536870911 1152921504606846975 1152921504606846974 1152921504606846973


Output


128
91
1600
505
0
1
502811676
264880351

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define For(i,s,a) for(lld i = (lld)s; i < (lld)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define sz size()
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ZAPS {int t; scanf("%i", &t); while(t--) solve();}
#define nieZAPS solve();
#define make_unique(x) (x).erase( unique(all(x)), (x).end())
 
 
template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

const int N = 5e5 + 1;

lld c[N];
lld at_least[61];
lld mod = 1e9 + 7;
lld potega[61];

void solve(void){
	memset(at_least, 0, sizeof(at_least));
	int n;
	scanf("%i", &n);
	For(i, 0, n)
		scanf("%lli", &c[i]);
	For(i, 0, n){
		For(j, 0, 61)
			if((1ll << j) & c[i])
				++at_least[j];
	}
	lld wyn = 0;
		
		
	For(i, 0, n){
		lld ory = 0;
		For(j, 0, 61)
			if((1ll << j) & c[i])
				ory = (ory + potega[j] * (lld)n) % mod;
			else
				ory = (ory + potega[j] * at_least[j]) % mod;
		lld andy = 0;
		For(j, 0, 61)
			if((1ll << j) & c[i])
				andy = (andy + potega[j] * at_least[j]) % mod;
		wyn = (wyn + ory * andy) % mod;
	}	
	printf("%lli\n", wyn);
}

int32_t main(void){
	
	For(i, 0, 61)
		potega[i] = (1ll << i) % mod;
	ZAPS
}

/*
0?1
2 3
*/

```