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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class Main {
	
	static int mod = 1000000007;
	
	//--------------------------------- Scanner --------------------------------------//
	
// 	public static class Scanner {
// 	    BufferedReader br;
// 	    StringTokenizer st;
// 	    public Scanner() {
// 	       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());
// 	    }
// 	    String nextLine(){
// 	        String str = "";
// 	    try {
// 	       str = br.readLine();
// 	    } catch (IOException e) {
// 	       e.printStackTrace();
// 	    }
// 	    return str;
// 	    }

// 	}
	
	// -------------------------- Print and Flush ------------------------------------ //
	
	public static void print(int[] arr) {
		for(int i=0 ; i<arr.length ; i++) System.out.print(arr[i]+" ");
		System.out.println();
	}
	
	public static void print(int[][] arr) {
		for(int i=0 ; i<arr.length ; i++) {
			for(int j=0 ; j<arr[0].length ; j++) System.out.print(arr[i][j]+" ");
			System.out.println();
		}
	}
	
	public static void print(int res) {
		System.out.println(res);
	}
	
	public static void print(String res) {
		System.out.println(res);
	}
	
	public static void print(int a , int b) {
		System.out.println(a + " " + b);
	}
	
	public static void print(char[] res) {
		for (int i = 0 ; i < res.length ; i++) 
			System.out.print(res[i]);
		System.out.println();
	}
	
	public static void flush() {
		System.out.flush();
	}
	
	// --------------------------- Is Palindrome ------------------------------------- //
	
	public static boolean isPalindrome(String str) {
		for (int i = 0 ; i < str.length() ; i++) { 
			if (str.charAt(i) != str.charAt(str.length() - i - 1))
				return false;
		}
		return true;
	}
	
	//-------------------------------- Pair ------------------------------------------ //
	
	public static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		Pair(Pair p) {
			x = p.x;
			y = p.y;
		}
	}
	
	//------------------------------- Comparator ------------------------------------ //
	
	static class cmp implements Comparator<int[]> {
		public int compare(int[] a , int[] b) {
			if (a[0] > b[0])
				return 1;
            else if (a[0] == b[0] && a[1] < b[1])
                return -1;
                
			return -1;
		}
	}
	
	// ----------------------------- Tries ------------------------------------------- //
	
	static class Tries {
		char ch = '\u0000';
		int count = 0;
		Tries[] arr = new Tries[26];
		boolean isEnd = false;
		Tries(char ch) {
			this.ch = ch;
		}
		Tries () { }
	}
	static Tries dummy = new Tries(); 
	static int tries_insert(String str) {
		Tries temp = dummy;
		for (int i = 0 ; i < str.length() ; i++) {
			int pos = str.charAt(i) - 'a';
			if (temp.arr[pos] == null) 
				temp.arr[pos] = new Tries(str.charAt(i));
			temp = temp.arr[pos];
		}
		temp.isEnd = true;
		temp.count += 1;
		return temp.count;
	}
	
	// ------------------------- Prime Number (seive) ------------------------------- //
	
	static int len = 10001;
	static int[] prime_number = new int[len];
	static Set<Integer> prime_number_set = new HashSet<>();
	static Set<Long> three_factor_set = new HashSet<>(); 
	static void seive() {
		prime_number[0] = 1;
		prime_number[1] = 1;
		for (int i = 2 ; i < len ; i++) {
			if (prime_number[i] == 0) {
				long val = i;
				prime_number_set.add(i);
				//three_factor_set.add(val * val);
				for (int j = i + i ; j < len ; j+=i) 
					prime_number[j] = 1;
			}
		}
	}
	
	static long[] product = new long[200001];
	static void multiply() {
		product[0] = 1;
		product[1] = 1;
		for (int i = 2 ; i < 200001 ; i++)
			product[i] = (product[i - 1] * i) % mod;
	}
	
	//--------------------------- perfect square ------------------------------------ //
	
	static Set<Integer> perfect_square = new HashSet();
	static void ps(int len) {
		for (int i = 1 ; i <= len ; i++) {
			perfect_square.add(i * i);
		}
	}
	
	
	// ---------------------------------- Sqrt -------------------------------------- //
		
	static long pow(long a , long b , long M) {
		if (b == 0)
			return 1;
		long mid = pow(a , b/2 , M) % M;
		if (b % 2 == 0) 
			return (mid * mid) % M;
		return (((mid * mid) % M) * a) % M;
	}
	
	static long sumDigit(long num) {
		long res = 0;
		while (num > 0) {
			res += num % 10;
			num = num / 10;
		}
		return res;
	}
	
	static long fact(int len , long M) {
		long res = 1;
		for (int i = 1 ; i < len ; i++) {
			res = (res * i) % M;
		}
		return res % M;
	}
	
	// ------------------------------- GCD ---------------------------------------- // 
	
	static long longGcd(long a , long b) {
		if (a > b) 
			longGcd(b , a);
		if (a == 0)
			return b; 
		return longGcd(b % a , a);
	}
    
    static int gcd(int a , int b) {
		if (a > b) 
			gcd(b , a);
		if (a == 0)
			return b; 
		return gcd(b % a , a);
	}
	
	
	// ----------------------------- LOWER BOND ------------------------------------ //
	
	static int upperBond(int[] arr , int target) {
		int st = 0 , end = arr.length - 1 , mid = 0;
		while (st < end) {
			mid = st + ((end - st) >> 1);
			if (arr[mid] < target) 
				st = mid + 1;
			else 
				end = mid;
		}
		return arr[end];
	}
	
	static int lowerBond(int[] arr , int target) {
		int st = 0 , end = arr.length - 1 , mid = 0;
		while (st < end) {
			mid = st + ((end - st) >> 1); 
			if (arr[mid] > target)
				end = mid - 1;
			else 
				st = mid;
		}
		return arr[st];
	}
    
    
    // --------------------------- print YES NO -------------------------------------//
    
    static void py() {
        System.out.println("YES");
    }
    
    static void pn() {
        System.out.println("NO");
    }
	
	
	// -------------------------- Solve --------------------------------------------- //
    static double dfs(double c , double m , double p , double v , double h) {
        
        
        if (c == 0 && m == 0)
           return p * h;
        
        if (c == 0) {
            double c2 = m <= v ? dfs(0 , 0 , p + m , v , h + 1) : dfs(0 , v , p + m - v , v , h + 1);
            return (m * c2) + (p * h);
        }
        
        if (m == 0) {
           double c1 = c <= v ? dfs(0 , 0 , p + c , v , h + 1) : dfs(v , 0 , p + c - v , v , h + 1);
            return (c * c1) + (p * h);
        }
        
        
        //System.out.println(m + ch + " " + m + " " + p);
        double c1 = c <= v ? dfs(0 , m + (c / 2) , p + (c / 2) , v , h + 1) : dfs(v , m + ((c - v) / 2) , p + ((c - v) / 2) , v , h + 1); 
        
        double c2 = m <= v ? dfs(c + (m / 2) , 0 , p + (m / 2) , v , h + 1) : dfs(c + ((m - v) / 2) , v , p + ((m - v) / 2) , v , h + 1);
        
        return  (c * c1) + (c * c2) + (p * h);
    }
    
    static int bs(int[] arr , int target) {
        int st = 0 , end = arr.length , mid = 0;
        
        while (st <= end) {
            mid = st + ((end - st) >> 1);
            
            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target) 
                st = mid + 1;
            else
                end = mid - 1;
        }
        
        return end;
    }
    
    static void merge(int[] arr , int st , int mid , int end , int[] index) {
        
        int leftSize = mid - st;
        int[] left = new int[leftSize];
        
        for (int i = 0 ; i < leftSize ; i++) {
            left[i] = index[i + st];
        }
        
        int rightSize = end - mid + 1;
        int[] right = new int[rightSize];
        
        
        for (int i = 0 ; i < rightSize ; i++) {
            right[i] = index[i + mid];
        }
        
        int l = 0 , r = 0 , k = st;
        while (l < leftSize && r < rightSize) {
            
            if (arr[left[l]] <= arr[right[r]]) {
                index[k] = left[l];
                k += 1;
                l += 1;
            } else {
                index[k] = right[r];
                k += 1;
                r += 1;
            }
            
        }
        
        while (l < leftSize) {
            index[k] = left[l];    
            k += 1;
            l += 1;
        }
        
        while (r < rightSize) {
            index[k] = right[r];
            k += 1;
            r += 1;
        }
        
    }
    
    
    static void mergeSort(int[] arr , int st , int end , int[] index) {
        
        if (st == end)
            return ;
        
        int mid = st + ((end - st) >> 1);
        
        mergeSort(arr , st , mid , index);
        mergeSort(arr , mid + 1 , end , index);
        
        merge(arr , st , mid + 1 , end , index);
    }
    
    
    
	public static void solve(Scanner s) {
        
        int n = s.nextInt();
        
        int x = 0 , y = 0 , z = 0;
        for (int i = 0 ; i < n ; i++) {
            x += s.nextInt();
            y += s.nextInt();
            z += s.nextInt();
        }
        
        if (x == 0 && y == 0 && z == 0)
            py();
        else
            pn();
	}
    
    public static void A(Scanner s) {
        
        int n = s.nextInt();
        
        long[] arr = new long[n];
        for (int i = 0 ; i < n ; i++) {
            arr[i] = s.nextLong();
        }
        
        long res = 0;
        for (int i = 0 ; i < n - 1 ; i++) {
            res = Math.max(res , arr[i] * arr[i + 1]);
        }
        
        System.out.println(res);
        
    }
    
    public static void B(Scanner s) {
        int n = s.nextInt();
        
        int k = s.nextInt();
        long[] arr = new long[n];
        for (int i = 0 ; i < n ; i++) 
            arr[i] = s.nextLong();
            
        
        long res = Long.MIN_VALUE;
        for (long i = n ; i >= Math.max(1 , n - 201) ; i--) 
            for (long j = i - 1 ; j >= Math.max(1 , n - 201) ; j--) 
                res = Math.max(res , (i * j) - (k * (arr[(int)(i - 1)] | arr[(int)(j - 1)])));
            
        System.out.println(res);
    }
    
    public static void C(Scanner s) {
        int n = ~(s.nextInt());
        int m = s.nextInt() + 1;
        
        int res = n & m;
        System.out.println(res);
        
    }
	
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
//	    PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
//	    multiply();
//		seive();
//		ps(1000000);
//		prime_number_set.add(1);
        int t = s.nextInt();
        //solve(s);
//	    s.nextLine();
	    while(t-->0) {
            
	    	//A(s);
            B(s);
            //C(s);
            //D(s);
            
        }

	    
//		e(s);
//	    int n      = s.nextInt();        // read input as integer
//	    long k     = s.nextLong();       // read input as long
//	    double d   = s.nextDouble();     // read input as double
//	    String str = s.next();           // read input as String
//	    String str2  = s.nextLine();       // read whole line as String
//	    long result = 3*k;
//	    out.println(result);                    // print via PrintWriter	   
//	    out.close();
	
	}
}

