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 B {
	static int[] arr;
	static int n;
	static int k;

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();

		int t = io.nextInt();
		for (int ii=0; ii<t; ii++) {
			n = io.nextInt();
			k = io.nextInt();

			arr = new int[n];

			for (int i=0; i<n; i++) {
				int x = io.nextInt();
				arr[i] = x;
			}

			long ans = Integer.MIN_VALUE;

			if (n <= 5000) {
				for (int i=0; i<n; i++) {
					for (int j=i+1; j<n; j++) {
						//System.out.println(f(i, j));
						ans = Math.max(ans, f(i, j));
					}
				}
				io.println(ans);
				continue;
			}

			if (n>5000) {
				for (int i=0; i<5000; i++) {
					for (int j=i+1; j<5000; j++) {
						long ret = f(n-1-i, n-1-j);
						ans = Math.max(ans, ret);
					}
				}

				io.println(ans);
				continue;
			}
		}
		io.close();
	}

	static long f(int a, int b) {
		long ret = (a+1)*(b+1) - (k* (arr[a] | arr[b]));
		return ret; 
	}

	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;

		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(new FileWriter(problemName + ".out"));
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}

		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}

		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
}