给你 $$$n$$$ 整数 $$$a_1、a_2、\ldots、a_n$$$ 和整数 $$$k$$$。求 $$$i \cdot j - k \cdot (a_i | a_j)$$$ 在所有 $$$(i, j)$$$ 且 $$$1 \le i < j \le n$$$ 的整数对上的最大值。这里,$$$|$$$ 是按位或运算符。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) 和 $$$k$$$ ($$$1 \le k \le \min(n, 100)$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$i \cdot j - k \cdot (a_i | a_j)$$$ 的最大可能值。
示例
输入 #1
4 3 3 1 1 3 2 2 1 2 4 3 0 1 2 3 6 6 3 2 0 0 5 6
输出 #1
-1 -4 3 12
注意
设 $$$f(i, j) = i \cdot j - k \cdot (a_i | a_j)$$$。
在第一个测试用例中,
- $$$f(1, 2) = 1 \cdot 2 - k \cdot (a_1 | a_2) = 2 - 3 \cdot (1 | 1) = -1$$$。
- $$$f(1, 3) = 1 \cdot 3 - k \cdot (a_1 | a_3) = 3 - 3 \cdot (1 | 3) = -6$$$。
- $$$f(2, 3) = 2 \cdot 3 - k \cdot (a_2 | a_3) = 6 - 3 \cdot (1 | 3) = -3$$$。
因此最大值为 $$$f(1, 2) = -1$$$。
在第四个测试用例中,最大值为 $$$f(3, 4) = 12$$$。