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.util.*;
import java.io.*;
import java.lang.*;
import java.math.BigInteger;

public class C {

  // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //

static FastReader  sc  = new FastReader();
static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws Exception {
//    try {

    int t = sc.nextInt();
    while (t-- > 0)
      C.go();
    out.flush();

}

static class pair{
	int  x,y;long z;
	pair(int x,int y,long z){
		this.x=x;
		this.y=y;
		this.z=z;
	}
}


static void go() {
int n=sc.nextInt();int k=sc.nextInt();
// I think this is a beauty of a question max value of a[i]|a[j] can be n 
// k max is 100 so i.j-100n. now we want i j to be max n*(n-1).
// but let j points to n then i.n - k*(a[i]|a[j]) a[i]=0 and [j]=0; so i.n-0.
// Now what we want i so that i.n > n*(n-1)-kn -> i> n-k-1.
int a[]=sc.intArray(n);
int l=Math.max(0,n-2*k);
long ans=Long.MIN_VALUE;
for(int i=l;i<n;i++) {
	for(int j=i+1;j<n;j++) {

		ans=Math.max(ans,(i+1)*1l*(j+1)-k*(a[i]|a[j]));
	}
}
out.println(ans);
}

static boolean check(int x,int y,int n,int m) {
	if(x>=n ||y>=m) {
		return false;
	}
	return true;
}

static int gcd(int a,int b) {
	if(b==0) {
		return a;
	}
	return gcd(b,a%b);
}


static boolean check(int x,int y,int n) {
	if(x<0||x>=n||y<0||y>=n) {
		return false;
	}
	return true;
}
static void   print(int a[][]) {
//out.println("--------");
for(int i=0;i<a.length;i++) {
	for(int j=0;j<a[i].length;j++) {
		if(a[i][j]==Integer.MAX_VALUE/2) {
			break;
		}
		out.print(a[i][j]+" ");
	}
	out.println();
}
}


  // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Ends <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //


static int mod = (int) 1e9 + 7;

// Returns nCr % p using Fermat's
// little theorem.
static long fac[];

static long ncr(int n, int r, int p) {

  if (n < r)
    return 0;
  // Base case
  if (r == 0)
    return 1;

  // Fill factorial array so that we
  // can find all factorial of r, n
  // and n-r

  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

private static long modInverse(long l, int p) {
  
  return pow(l,p-2);
}

static void sort(long[] a) {
  ArrayList<Long> aa = new ArrayList<>();
  for (long i : a) {
    aa.add(i);
  }
  Collections.sort(aa);
  for (int i = 0; i < a.length; i++)
    a[i] = aa.get(i);
}
static void sort(int[] a) {
  ArrayList<Integer> aa = new ArrayList<>();
  for (int i : a) {
    aa.add(i);
  }
  Collections.sort(aa);
  for (int i = 0; i < a.length; i++)
    a[i] = aa.get(i);
}
static long pow(long x, long y) {
  long res = 1l;
  while (y != 0) {
    if (y % 2 == 1) {
      res = x * res % mod;
    }
    y /= 2;
    x = (x * x) % mod;
  }
  return res;
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //

static class FastReader {
  BufferedReader  br;
  StringTokenizer st;

  public FastReader() {
    br = new BufferedReader(new InputStreamReader(System.in));
  }

  String next() {
    while (st == null || !st.hasMoreElements()) {
      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());
  }

  double nextDouble() {
    return Double.parseDouble(next());
  }
	int[] intArray(int n) {
		int a[]=new int[n];
		for(int i=0;i<n;i++)a[i]=sc.nextInt();
		return a;
	}
	long[] longArray(int n) {
		long a[]=new long[n];
		for(int i=0;i<n;i++)a[i]=sc.nextLong();
		return a;
	}
  String nextLine() {
    String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }

}


//use this for double quotes inside string
// " \"asdf\""
