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
import sys
testing = len(sys.argv) == 4 and sys.argv[3] == "myTest"
if testing:
    cmd = sys.stdout
    from time import time
    start_time = int(round(time() * 1000)) 
    input = open(sys.argv[1], 'r').readline
    sys.stdout = open(sys.argv[2], 'w')
else:
    input = sys.stdin.readline
mod = 10**9+7
# from math import ceil
# from collections import defaultdict as dd
# from heapq import *
############ ---- I/O Functions ---- ############
def intin():
    return(int(input()))
def intlin():
    return(list(map(int,input().split())))
def chrin():
    s = input()
    return(list(s[:len(s) - 1]))
def strin():
    s = input()
    return s[:len(s) - 1]
def intlout(l, sep=" "):
    print(sep.join(map(str, l)))

def main():
    n = intin()
    a = intlin()
    b = [format(x,'b')[::-1] for x in a]
    lens = [len(x) for x in b]
    maxK = max(lens)
    bcnt = [0]*maxK
    for i in xrange(n):
        x = b[i]
        for k in xrange(lens[i]):
            if x[k]=='1':
                bcnt[k] += 1
    kpowb = [(((1<<k)%mod)*bcnt[k])%mod for k in xrange(maxK)]
    summ = sum(kpowb)%mod   # sum(a)
    ans = 0
    for j in xrange(n):
        x = b[j]
        tmp = 0
        for k in xrange(lens[j]):
            if x[k] == '1':
                tmp += kpowb[k]
        tmp %= mod
        ans = (ans + (tmp*(((a[j]%mod)*n)%mod + summ - tmp)%mod)%mod)%mod
    # print(ans)
    return(ans)

if __name__ == "__main__":
    ans = []
    for _ in xrange(intin()):
        ans.append(main())
        # main()
        # print("YES" if main() else "NO")
    intlout(ans,'\n')
    # main()

    if testing:
        sys.stdout = cmd
        print(int(round(time() * 1000))  - start_time)