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.
/*==============================================
Author      : Shadman Shariar                 ||
Email       : shadman.shariar@northsouth.edu  ||
University  : North South University (NSU)    ||
Facebook    : shadman.shahriar.007            ||
==============================================*/
import java.io.*;
import java.util.*;
//import java.math.BigInteger;
//import java.text.DecimalFormat;
public class Main {
public static Main obj = new Main();
//public static FastReader fr = new FastReader();
//public static Scanner input = new Scanner(System.in);
//public static PrintWriter pw = new PrintWriter(System.out);
//public static DecimalFormat df = new DecimalFormat(".000");
//public static BufferedReader br = new BufferedReader
//(new InputStreamReader(System.in));
public static void main (String[] args) throws Exception {
Scanner input = new Scanner (System.in);
//BigInteger bi = new BigInteger("000");
//StringBuilder sb = new StringBuilder();
//StringBuffer sbf = new StringBuffer();
//StringTokenizer st = new StringTokenizer("String","Split");
 
/** Array List, Linked List, Vector
 *  Stack, Queue, Array Deque, Priority Queue
 *  Hash Set, Linked Hash Set, Tree Set [Comparator]
 *  Hash Map, Linked Hash Map, Tree Map [Comparator] */ 

//-----------------CODE STARTS FROM HERE------------------//

long tt = input.nextLong();

for (long zz = 0; zz < tt ; zz++) {
	 
	long n = input.nextLong();
	
	
	long k = input.nextLong();
	
	long [] arr=  new long[(int) (n+1)];

    for (int i = 1; i <= n; i++) {
		
    	arr[i] = input.nextLong();
    	
    	
	}
	
    long ans = (n * (n - 1)) - (k *((arr[(int) n] | arr[(int) (n - 1)])));
//    long max = Long.MIN_VALUE;
      for (int j = (int) n; j > 0 ; j--) {
		
    	 for (int i = j-1; i > 0; i--) {
			
    		 if((i*j)<=ans) 
    			 break;
    		 
    			
    			ans = Math.max(ans, ((j * i) - (k * (arr[j] | arr[i])))); 
    		 
    		 
		}
    	  
	}
    
    System.out.println(ans);
	
}

//---------------------CODE ENDS HERE---------------------//
 
        //pw.close();
        input.close();
		System.exit(0);
}

   public static long gcd(long a, long b) {
	   if (a == 0)
		   return b;
	   return gcd(b % a, a);
   }
 
   public static long lcm(long a, long b) {
	   return (a / gcd(a, b)) * b;
   }
 
   public static long nCr(long n, long r)
   {
       return factorial(n) / (factorial(r) *
                  factorial(n - r));
   }
 
   public static long nPr(long n, long r)
   {
    return factorial(n) / factorial(n - r);
   }
 
   public static long countsubstring(String str)
   {
    long n = str.length();
    return n * (n + 1) / 2;
   }
 
   public static boolean ispalindrome(String str)
   {
    int i = 0, j = str.length() - 1;
    while (i < j) {
        if (str.charAt(i) != str.charAt(j))
            return false;
        i++;
        j--;
    }
    return true;
   }
 
   public static boolean perfectsquare(long x)
   {
    if (x >= 0) {
        long sr = (long)(Math.sqrt(x));
        return ((sr * sr) == x);
    }
    return false;
   }
 
   public static boolean perfectcube(long N)
   {
    int cube; int c = 0;
    for (int i = 0; i <= N; i++) {
        cube = i * i * i;
        if (cube == N) {
           
            c=1; break;
        }
        else if (cube > N) {
          
           c=0 ; break ;
        }
    }
	  if (c==1)return true;
	  else return false;
   }
 
   public static int divcount(int n)
   {
       boolean hash[] = new boolean[n + 1];
       Arrays.fill(hash, true);
       for (int p = 2; p * p < n; p++)
           if (hash[p] == true)
               for (int i = p * 2; i < n; i += p)
                   hash[i] = false;
       int total = 1;
       for (int p = 2; p <= n; p++) 
       {
           if (hash[p])
           {
               int count = 0;
               if (n % p == 0) 
               {
                   while (n % p == 0) 
                   {
                       n = n / p;
                       count++;
                   }
                   total = total * (count + 1);
               }
           }
       }
       return total;
   }
   
   public static void printdiv(int n)
  {
      for (int i=1; i<=Math.sqrt(n); i++)
      {
          if (n%i==0)
          {
              if (n/i == i)
                  System.out.print(" "+ i);
    
              else
                  System.out.print(i+" " + n/i + " " );
          }
      }
  }
  
   public static boolean[] sieveOfEratosthenes(int n)
   {
    boolean prime[] = new boolean[n + 1];
    for (int i = 0; i <= n; i++)
        prime[i] = true;
 
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    prime[1]=false;
    return prime;
   }
	
   public static int removeduplicateelements(int arr[], int n){ 
		Arrays.sort(arr);
        if (n==0 || n==1){  
            return n;  
        }  
        int[] temp = new int[n];  
        int j = 0;  
        for (int i=0; i<n-1; i++){  
            if (arr[i] != arr[i+1]){  
                temp[j++] = arr[i];  
            }  
         }  
        temp[j++] = arr[n-1];      
        for (int i=0; i<j; i++){  
            arr[i] = temp[i];  
        }  
        return j;  
    }  
	
   public static int fibon(int n) {
 
		if (n <= 1) {
 
			return n;
		}
		int[] array = new int[n + 1];
		array[0] = 0;
		array[1] = 1;
		for (int i = 2; i <= n; i++) {
			array[i] = array[i - 2] + array[i - 1];
		}
 
		return array[n];
 
	}
 
   public static long sumofdigits(long n) {
		long sum = 0;
 
		while (n != 0) {
			sum = sum + n % 10;
			n = n / 10;
		}
 
		return sum;
	}
 
   public static int reversedigits(int num) {
		int rev_num = 0;
		while (num > 0) {
			rev_num = rev_num * 10 + num % 10;
			num = num / 10;
		}
		return rev_num;
	}
 
   public static int binarysearch(int arr[], int l, int r, int x) {
 
		if (r >= l) {
			int mid = l + (r - l) / 2;
			if (arr[mid] == x)
				return mid;
			if (arr[mid] > x)
				return binarysearch(arr, l, mid - 1, x);
			return binarysearch(arr, mid + 1, r, x);
		}
		return -1;
	}
 
   public static void rangeofprimenumber(int a, int b) {
		int i, j, flag;
		for (i = a; i <= b; i++) {
			if (i == 1 || i == 0)
				continue;
			flag = 1;
			for (j = 2; j <= i / 2; ++j) {
				if (i % j == 0) {
					flag = 0;
					break;
				}
			}
			if (flag == 1)
				System.out.println(i);
		}
	}
 
   public static boolean isprime(long n) {
		if (n <= 1)
			return false;
		else if (n == 2)
			return true;
		else if (n % 2 == 0)
			return false;
		for (long i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
 
   public static long factorial(long n) {
		return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
	}
 
   public static int[] reversearrayinrange(int arr[], int start, int end) {
		int temp;
 
		while (start < end) {
			temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}
	  return arr;
	}
 
   public 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());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}