Cobb solution codeforces

Cobb solution codeforces


You are given nn integers a1,a2,,ana1,a2,…,an and an integer kk. Find the maximum value of ijk(ai|aj)i⋅j−k⋅(ai|aj) over all pairs (i,j)(i,j) of integers with 1i<jn1≤i<j≤n. Here, || is the bitwise OR operator.

Input

The first line contains a single integer tt (1t100001≤t≤10000)  — the number of test cases.

The first line of each test case contains two integers nn (2n1052≤n≤105) and kk (1kmin(n,100)1≤k≤min(n,100)).

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

It is guaranteed that the sum of nn over all test cases doesn’t exceed 31053⋅105.

Output

For each test case, print a single integer  — the maximum possible value of ijk(ai|aj)i⋅j−k⋅(ai|aj).

Example

input

Copy
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

output

Copy
-1
-4
3
12
Note

Let f(i,j)=ijk(ai|aj)f(i,j)=i⋅j−k⋅(ai|aj).

In the first test case,

  • f(1,2)=12k(a1|a2)=23(1|1)=1f(1,2)=1⋅2−k⋅(a1|a2)=2−3⋅(1|1)=−1.
  • f(1,3)=13k(a1|a3)=33(1|3)=6f(1,3)=1⋅3−k⋅(a1|a3)=3−3⋅(1|3)=−6.
  • f(2,3)=23k(a2|a3)=63(2|3)=3f(2,3)=2⋅3−k⋅(a2|a3)=6−3⋅(2|3)=−3.

So the maximum is f(1,2)=1f(1,2)=−1.

In the fourth test case, the maximum is f(3,4)=12f(3,4)=12.


Leave a Comment