D. Max MST
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Captain Kareem Elgoker is establishing a new pirate haven in the treacherous Algorithmic Seas. He has obtained an ancient map detailing the locations of $$$n$$$ uncharted islands. Due to the mystical properties of the ocean, each island emits a unique magnetic signature, denoted by an integer $$$a_i$$$.

The Captain must select exactly $$$k$$$ of these islands to form his secret archipelago territory. To ensure his crew can travel safely without being detected by the Royal Navy, he must connect all $$$k$$$ chosen islands into a single continuous network using hidden smuggling routes.

A smuggling route can be established between any two selected islands $$$u$$$ and $$$v$$$. The "Secrecy Level" (cost) of the route between island $$$u$$$ and island $$$v$$$ is exactly the Least Significant Bit (LSB) of the absolute difference of their magnetic signatures.

Formally, the weight of the edge between $$$u$$$ and $$$v$$$ is $$$LSB(\vert{}a_u - a_v\vert{})$$$.

(Note: $$$LSB(x)$$$ is the largest power of $$$2$$$ that divides $$$x$$$. For example, $$$LSB(12) = 4$$$, and $$$LSB(7) = 1$$$.)

To build a secure base, the network of islands will be connected by its Minimum Spanning Tree (MST) based on these Secrecy Levels. However, to maximize the overall obscurity of his territory, Captain Kareem wants to select the subset of $$$k$$$ islands such that the total weight of this MST is maximized.

Given the array $$$a$$$ representing the magnetic signatures of the islands, find the maximum possible weight of the MST if the Captain optimally chooses exactly $$$k$$$ islands.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$) — the total number of islands and the number of islands Captain Kareem must select.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \lt 2^{30}$$$) — the magnetic signatures of the islands.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum possible weight of the Minimum Spanning Tree formed by choosing exactly $$$k$$$ islands.

Example
Input
3
5 3
10 7 14 6 24
4 4
1 2 3 4
6 4
2 4 8 16 32 64
Output
8
3
24