The company of gums and lollipops has exactly $$$k$$$ types of employees numbered from $$$0$$$ to $$$k-1$$$. The employees of the company are split into $$$n$$$ squads. The $$$i$$$-th squad is represented as an integer number $$$a_i$$$ where the squad has an employee of the $$$j$$$-th type iff the $$$j$$$-th bit in the binary representation of $$$a_i$$$ equals $$$1$$$.
The efficiency of the $$$i$$$-th type of employees equals $$$2^i$$$ iff each of the $$$n$$$ squads has an employee of the $$$i$$$-th type. Otherwise, it's $$$0$$$.
The efficiency of the company of gums and lollipops is the sum of efficiencies of all of the employee types the company has.
Philip is the manager of the company. Everyone thinks that he is not a good manager because of his profile picture, so he wanted to prove them wrong and do some changes that would increase the efficiency of the company.
For each $$$i$$$ from $$$1$$$ to $$$n$$$, he will choose $$$\textbf{exactly}$$$ one of the following operations and perform it on the squad $$$\textbf{exactly}$$$ once:
He wants to do the operations so that the efficiency of the company is maximized. He is really a kid who does not know what he is doing, so he assigned this task to you as the assistant manager of the company of gums and lollipops. Go on and prove them wrong so that Philip is not a kid in people's opinion.
The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^4)$$$. The number of test cases.
The first line of each test case contains two space-separated integer numbers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 2 \times 10^5, 1 \le k \le 30)$$$. The number of squads in the company of gums and lollipops and the number of types of employees of the company, respectively.
The second line of each test case contains $$$n$$$ space-separated integer numbers $$$a_1, a_2 \dots a_n$$$ $$$(0 \le a_i < 2^k)$$$, where the $$$i$$$-th integer number is the number assigned to the $$$i$$$-th squad.
It is guaranteed that the sum of $$$n$$$ over all of the test cases does not exceed $$$2 \times 10^5$$$.
For each test case print a single integer number in a single line. The maximum efficiency of the company of gums and lollipops.
25 41 2 9 15 42 22 2
8 3
In the first test case, there are four types of employees and there are five squads.
- The first squad has only one employee of type $$$0$$$.
- The second squad has only one employee of type $$$1$$$.
- The third squad has two employees of types $$$0$$$ and $$$3$$$.
- The forth squad has four employees of types $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$.
- The fifth squad has one employee of type $$$2$$$.
It's ideal to do the following operations:
- Add an employee of type $$$3$$$ to the first squad.
- Add an employee of type $$$3$$$ to the second squad.
- Remove the employee of type $$$0$$$ from the third squad.
- Remove the employee of type $$$2$$$ from the forth squad.
- Add an employee of type $$$3$$$ to the fifth squad.
After these operations, the only type that all squads has one employee of is type $$$3$$$, so the answer is $$$2^3 = 8$$$.
In the second test case, you can add one employee of type $$$0$$$ to each squad. After the operations, all squads have one employee of type $$$0$$$ and $$$1$$$, so the answer is $$$2^0 + 2^1 = 1 + 2 = 3$$$.
