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.
//------------------>>>>>>>>>>>>>>>> HI . HOW ARE YOU? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<------------------------------

import java.io.*;
import java.util.*;
import java.util.List;
import java.util.StringTokenizer;

//---------------------------->>>>>>>>>>>>>>>>>>>>>> FK OFF <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<-------------------

//--------------------------->>>>>>>>>>>>>>>>>>>>>>>> HACKER MF <<<<<<<<<<<<-------------------------------------

public class practice{

    static int[] count,count1,count2;
    static boolean[] prime;
    static boolean flag;
    static int[] spf;
    static Node[] nodes,nodes1,nodes2;
    static long[] arr;
    static long[][] cost;
    static int[] arrInt,darrInt,farrInt;
    static int[][] dp;
    static char[] ch,ch1,ch2;
    static long[] darr,farr;
    static int[][] mat,mat1;
    static boolean[] vis;
    static long x,h;
    static long maxl,sum,total;
    static double dec;
    static long mx = (long)1e7;
    static long inf = (long)1e17;
    static String s,s1,s2,s3,s4;
    static long minl;
    static long mod = (long)(1e9)+7;
    // static int minl = -1;
    // static long n;
    static int n,n1,n2,q,r1,c1,r2,c2;
    static int arr_size = (int)2e5+10;
    static long a;
    static long b;
    static long c;
    static long d;
    static long y,z;
    static int m,m1;
    static long ans;
    static long k;
    static FastScanner sc;
    static String[] str,str1;
    static Set<Long> set,set1,set2;
    static SortedSet<Long> ss;
    static List<StringBuilder> list,list1,list2,list3;
    static PriorityQueue<Node> pq,pq1;
    static LinkedList<Node> ll,ll1,ll2;
    static Map<Integer,List<Integer>> map;
    static Map<Integer,Integer> map2;
    static Map<Integer,Long> mapL,mapR;
    static Map<Integer,Node> map1;
    static StringBuilder sb,sb1,sb2;
    static int index;
    static int[] dx = {0,-1,0,1,-1,1,-1,1};
    static int[] dy = {-1,0,1,0,-1,-1,1,1};

    static class Node{
        int first;
        int second;
        Node(int f,int s){
            this.first = f;
            this.second = s;
        }
    }

    static LNode head = null;
    static LNode tail = null;

    static class LNode{
        long key;
        long val;
        LNode next;
        LNode prev;
        LNode(long key,long val){
            this.key = key;
            this.val = val;
            this.next = null;
            this.prev = null;
        }
        LNode(long val){
            this.key = -1;
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }


//     public static void solve(){
//
//        FastScanner sc = new FastScanner();
//        int t = sc.nextInt();
//        // int t = 1;
//        for(int tt = 1 ; tt <= t ; tt++){
//
//            System.out.println("Case #"+tt+": "+ ans);
//
//        }
//
//     }

    //--------------->>>>IF YOU ARE HERE FOR QUICKSORT HACK THEN SORRY NO HACK FOR YOU<<<-------------------------------

    public static void solve(){

        long ans = -inf;
        long k = m;

        for(int i = 1 ; i < n ; i++){

            int j = i-1;
            long or = arr[i] | arr[j];
            long maxGain = or - arr[i];
            ans = max(ans, (long) ((long)(i+1)) *(j+1) - k*(or));
            long loss = 0;
            long gain = 0;

            for(j = i-2 ; j > -1 ; j--){
                or = arr[i] | arr[j];
                gain = or - arr[i];
                loss += i;
                ans = max(ans, (long) ((long)(i+1)) *(j+1) - k*(or));
                if(loss > maxGain)
                    break;
            }

        }

        sb.append(ans).append("\n");

    }

    //----------->>>>>>> SPEED UP SPEED UP . THIS IS SPEEDFORCES . SPEED UP SPEEEEEEEEEEEEEEEEEEEEEEEEEEDDDDDD <<<<<<<------------------

    public static void main(String[] args) {

        sc = new FastScanner();
        // Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        int t = sc.nextInt();
//        int t = 1;
        while(t > 0){

//             k = sc.nextLong();
            // x = sc.nextLong();
            // y = sc.nextLong();
            // z = sc.nextLong();

//            a = sc.nextLong();
//             b = sc.nextLong();
//             c = sc.nextLong();
//             d = sc.nextLong();
//
//             x = sc.nextLong();
//             y = sc.nextLong();
//             z = sc.nextLong();
            // d = sc.nextLong();

            n = sc.nextInt();

            // n1 = sc.nextInt();

//            m = sc.nextInt();
//             q = sc.nextInt();

//             a = sc.nextLong();
//             b = sc.nextLong();

//             k = sc.nextLong();

//            x = sc.nextLong();
            // d = sc.nextLong();

//            s = sc.next();

//            ch = sc.next().toCharArray();
//            ch1 = sc.next().toCharArray();

             m = sc.nextInt();
            // n = 6;

            arr = new long[n];
            for(int i = 0 ; i < n ; i++){
                arr[i] = sc.nextLong();
            }

//            arrInt = new int[n];
//            for(int i = 0 ; i < n ; i++){
//                arrInt[i] = sc.nextInt();
//            }

            // x = sc.nextLong();
            // y = sc.nextLong();
//             ch = sc.next().toCharArray();
//            m = n;
////             m = sc.nextInt();
//            darr = new long[m];
//            for(int i = 0 ; i < m ; i++){
//                darr[i] = sc.nextLong();
//            }
            // k = sc.nextLong();
            // m = n;
//             darrInt = new int[n];
//             for(int i = 0 ; i < n ; i++){
//                 darrInt[i] = sc.nextInt();
//             }

//             farr = new long[n];
//             for(int i = 0 ; i < n ; i++){
//                 farr[i] = sc.nextLong();
//             }

            // farrInt = new int[m];
            // for(int i = 0; i < m ; i++){
            //     farrInt[i] = sc.nextInt();
            // }

            // m = n;
//            mat = new int[n][5];
//            for(int i = 0 ; i < n ; i++){
//                for(int j = 0 ; j < 5 ; j++){
//                    mat[i][j] = sc.nextInt();
//                }
//            }

//             m = n;
//             mat = new char[n][m];
//             for(int i = 0 ; i < n ; i++){
//                 String s = sc.next();
//                 for(int j = 0 ; j < m ; j++){
//                     mat[i][j] = s.charAt(j);
//                 }
//             }
//
//             str = new String[n];
//             for(int i = 0 ; i < n ; i++)
//                 str[i] = sc.next();

//             nodes = new Node[n];
//             for(int i = 0 ; i < n ;i++)
//                 nodes[i] = new Node(sc.nextLong(),(i));

            solve();
            t -= 1;
        }
        System.out.print(sb);

    }

    public static int log(double n,double base){

        if(n == 0 || n == 1)
            return 0;

        if(n == base)
            return 1;

        double num = Math.log(n);
        double den = Math.log(base);

        if(den == 0)
            return 0;

        return (int)(num/den);
    }

    public static boolean isPrime(long n) {
        // Corner cases
        if (n <= 1)
            return false;

        if (n <= 3)
            return true;

        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n%2 == 0 || n%3 == 0)
            return false;

        for (int i=5; i*i<=n; i=i+6)
            if (n%i == 0 || n%(i+2) == 0)
                return false;

        return true;
    }

    public static void SpecialSieve(int MAXN)
    {
        spf = new int[MAXN];
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)

            // marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;

        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)

                    // marking spf[j] if it is not
                    // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }

    public static ArrayList<Integer> getFactorization(int x)
    {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        while (x != 1)
        {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }

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

    public static long lcm(long a, long b)
    {
        return (b/gcd(b, a % b)) * a;
    }

    public static long mod_inverse(long a,long mod){
        long x1=1,x2=0;
        long p=mod,q,t;
        while(a%p!=0){
            q = a/p;
            t = x1-q*x2;
            x1=x2; x2=t;
            t=a%p;
            a=p; p=t;
        }
        return x2<0 ? x2+mod : x2;
    }

    public static void swap(double[] curr,int i,int j){
        double temp = curr[j];
        curr[j] = curr[i];
        curr[i] = temp;
    }

    static final Random random=new Random();

    static void ruffleSortLong(long[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            long temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSortInt(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            int temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSortChar(char[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            char temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static long binomialCoeff(long n, long k){

        long res = 1;

        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;

        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (long i = 0; i < k; ++i) {
            res = (res*(n - i));
            res = (res/(i + 1));
        }

        return res;
    }

    static long mod(long x)
    {
        long y = mod;
        long result = x % y;
        while (result < 0)
        {
            result += y;
        }
        return result;
    }

    static long[] fact;

    public static long inv(long n){
        return power(n, mod-2);
    }

    public static void fact(int n){
        fact = new long[n+1];
        fact[0] = 1;
        for(int j = 1;j<=n;j++)
            fact[j] = (fact[j-1]*(long)j)%mod;
    }

    public static long binom(int n, int k){

        long prod = fact[n];
        prod*=inv(fact[n-k]);
        prod%=mod;
        prod*=inv(fact[k]);
        prod%=mod;
        return prod;
    }

    static long power(long x, long y){
        if (y == 0)
            return 1;
        if (y%2 == 1)
            return (x*power(x, y-1))%mod;
        return power((x*x)%mod, y/2)%mod;
    }

    static void sieve(int n){

        prime = new boolean[n+1];
        for(int i=2;i<n;i++)
            prime[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p])
            {
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }

    }

    static long abs(long a){
        return Math.abs(a);
    }

    static int abs(int a){
        return Math.abs(a);
    }

    static int max(int a,int b){
        if(a>b)
            return a;
        else
            return b;
    }
    static double max(double a,double b){
        if(a>b)
            return a;
        else
            return b;
    }
    static double min(double a,double b){
        if(a>b)
            return b;
        else
            return a;
    }

    static int min(int a,int b){
        if(a>b)
            return b;
        else
            return a;
    }

    static long max(long a,long b){
        if(a>b)
            return a;
        else
            return b;
    }

    static long min(long a,long b){
        if(a>b)
            return b;
        else
            return a;
    }

    static long sq(long num){
        return num*num;
    }

    static double sq(double num){
        return num*num;
    }

    static long sqrt(long num){
        return (long)Math.sqrt(num);
    }

    static double sqrt(double num){
        return Math.sqrt(num);
    }

    static private void removeNode(LNode n){
        if(n.prev!=null){
            n.prev.next = n.next;
        }else{
            head = n.next;
        }

        if(n.next!=null){
            n.next.prev = n.prev;
        }else{
            tail = n.prev;
        }
    }

    static private void offerNode(LNode n){

        if(tail!=null){
            tail.next = n;
        }

        n.prev = tail;
        n.next = null;
        tail = n;

        if(head == null){
            head = tail;
        }
    }

    static class FastScanner {

        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());
        }
        //        void readArray(int n) {
//            arr = new long[n];
//            for (int i = 0; i < n; i++)
//                arr[i] = nextLong();
//        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }

}