human
PYTHON3 solution for "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.":
assistant
#Here is Python code to find the maximum value of i ⋅ j - k ⋅ (a_i | a_j) over all pairs (i, j) of integers with 1 ≤ i < j ≤ n.
 from math import *
from decimal import *
from decimal import Decimal as D
from string import ascii_lowercase as lc
from string import ascii_uppercase as uc
from itertools import *
from itertools import permutations as perm
from itertools import product as prod
from sys import *
ip = input
ra = lambda: list(map(int, input().split()))
ri = lambda: int(input())
rd = lambda: map(int, input().split())
MOD = 10 ** 9 + 7
MOD2 = 998244353
maxn = 10 ** 6 + 10
N = 10 ** 5 + 10
N2 = 2 * 10 ** 5
getcontext().prec = 20
inf = 1 << 65
def debug(*a, sep=' ', end='\n'):
    stderr.write(sep.join(map(str, a)) + end)
def fp(x, p, m):
    r = 1
    while p:
        if p % 2:
            r = r * x % m
            p -= 1
        else:
            x = x * x % m
            p //= 2
    return r
def fact(x, m):
    r = 1
    for i in range(2, x + 1):
        r = r * i % m
    return r
def C(n, k, m):
    return fact(n, m) * fp(fact(n - k, m), m - 2, m) % m * fp(fact(k, m), m - 2, m) % m
class SegmentTree:
    def f(self, a, b):
        return a + b
    def __init__(self, n, a):
        self.tree = [0] * (2 * n)
        self.n = n
        for i in range(n):
            self.tree[n + i] = a[i]
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.f(self.tree[2 * i], self.tree[2 * i + 1])
    def q(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while r > 1:
            if l % 2:
                res = self.f(res, self.tree[l]) 
                l += 1
            if r % 2:
                r -= 1
                res = self.f(res, self.tree[r])
            r //= 2
            l //= 2
        return res
    def u(self, index, value):
        index += self.n
        self.tree[index] = value
        index //= 2
        while index > 0:
            self.tree[index] = self.f(self.tree[2 * index], self.tree[2 * index + 1])
            index //= 2
def z_function(s):
    l, r, n = 0, 0, len(s)
    z = [0] * n
    z[0] = 0
    for i in range(1, n):
        if r >= i: z[i] = min(z[i - l], r - i + 1)
     ...