Today, Yuta gives Rikka a simple math task: given a positive integer array A of length n and a positive integer m, does the equation have any solutions?

Rikka solves this problem easily: is always a solution of this equation.

And then, Yuta shows a much harder version of this task:

For a positive integer array A of length n and a positive integer m, let f(A,m) be the number of different integer vectors x which satisfy x_i ∈ [0,m) and .

For example, when A=[1,1], m=2, there are 2 integer vectors [0,0],[1,1] satisfy the previous conditions. So f([1,1],2) is equal to 2.

Now Yuta shows a positive integer array B of length n and a positive integer M. B has N=2ⁿ-1 non-empty subsequences A₁,...,A_N. For each integer m ∈ [1,M], Yuta wants to know .

For example, when B=[1,1] and M = 3, Rikka needs to calculate f([1],1) x 2 + f([1,1],1), f([1],2) x 2 + f([1,1],2) and f([1],3) x 2 + f([1,1],3).

This task is too hard for Rikka. So she wants you to help her.

The first line contains a single integer t(1 ≤ t ≤ 3), the numebr of the testcases.

For each testcase, the first line contains two integers n,M(1 ≤ n,M ≤ 105). The second line contains n positive integers Bi(1 ≤ Bi ≤ 105).

For each testcase, let wm be equal to . You only need to output a single line with a single integer, , i.e., the exclusive OR sum of all wi.

2
5 5
1 2 3 4 5
10 10
1 2 3 4 5 6 7 8 9 10

1079
933958261