You are given n integers a_1, a_2, …, a_n and an integer k. Find the maximum value of i ⋅ j - k ⋅ (a_i | a_j) over all pairs (i, j) of integers with 1 ≤ i < j ≤ n. Here, | is the [bitwise OR operator](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains two integers n (2 ≤ n ≤ 10^5) and k (1 ≤ k ≤ min(n, 100)).

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ n).

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case, print a single integer — the maximum possible value of i ⋅ j - k ⋅ (a_i | a_j).

Example

Input


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


-1
-4
3
12

Note

Let f(i, j) = i ⋅ j - k ⋅ (a_i | a_j).

In the first test case, 

  * f(1, 2) = 1 ⋅ 2 - k ⋅ (a_1 | a_2) = 2 - 3 ⋅ (1 | 1) = -1. 
  * f(1, 3) = 1 ⋅ 3 - k ⋅ (a_1 | a_3) = 3 - 3 ⋅ (1 | 3) = -6. 
  * f(2, 3) = 2 ⋅ 3 - k ⋅ (a_2 | a_3) = 6 - 3 ⋅ (1 | 3) = -3. 



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

In the fourth test case, the maximum is f(3, 4) = 12.
import java.io.*;
import java.util.*;



/*

*/

public class A {
	static FastReader sc=null;
	
	public static void main(String[] args) {
		sc=new FastReader();
		int t=sc.nextInt();
		PrintWriter out=new PrintWriter(System.out);
		while(t-->0) {
			int n=sc.nextInt(),k=sc.nextInt(),
					m=Integer.numberOfTrailingZeros(Integer.highestOneBit(2*n+1)),nax=(1<<m);
			int a[]=sc.readArray(n);
			Pair p[]=new Pair[nax];
			for(int i=0;i<nax;i++)p[i]=new Pair(-1,-1);
			for(int i=0;i<n;i++)p[a[i]]=combine(p[a[i]],new Pair(i,-1));
			
			//for this ai|aj what is the maximum we can get
			//the or value will be k if we or k with any of its submasks
			
			for(int i=0;i<m;i++) {
				for(int mask=0;mask<nax;mask++) {
					if((mask&(1<<i))>0) {
						p[mask]=combine(p[mask],p[mask^(1<<i)]);
					}
				}
			}
			long ans=Long.MIN_VALUE;
			for(int mask=0;mask<nax;mask++) {
				if(p[mask].l!=-1) {
					ans=Math.max(ans, get(mask,p[mask],k));
				}
			}
			out.println(ans);
			
		}
		out.close();
		
		
		
		
	}
	static long get(int mask,Pair p,int k) {
		return (p.l+1)*1L*(p.r+1) - k*1L*mask;
	}
	static class Pair{
		int l,r;
		Pair(int l,int r){
			this.l=l;
			this.r=r;
		}
	}
	static Pair combine(Pair a,Pair b) {
		int v[]= {a.l,a.r,b.l,b.r};
		Arrays.sort(v);
		return new Pair(v[2],v[3]);
	}
	
	
	static int[] ruffleSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al);
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
		return a;
	}
	static void print(int a[]) {
		for(int e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	
	static class FastReader{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while(!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				}
				catch(IOException e){
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int[] readArray(int n) {
			int a[]=new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			return a;
		}
	}
}






