K. Land Distribution
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a rooted family tree having $$$n$$$ nodes. Each node in this tree (except the root) has a unique parent. Node $$$1$$$ is the root of the tree. Initially, the root owns $$$k$$$ units of land.

Each generation, all nodes which own positive amount of land and have at least one children, have to distribute all of the land among their children. Each child must receive an integral amount of land. Also, the minimum amount of land received by any child and the maximum amount of land received by any child (of the same parent) must not differ by more than $$$1$$$.

Let $$$a_i$$$ $$$(2 \le i \le n)$$$ be the amount of land received by the node $$$i$$$ from their parent and $$$a_1 = k$$$. Over all possible ways of distributing the land, find the maximum possible value of $$$$$$\displaystyle\sum_{i=1}^{n} (a_i \oplus i)$$$$$$

Note that $$$a_i$$$ represents the amount of land received by node $$$i$$$ from their parent, not the final amount of land it owns.

Here, $$$\oplus$$$ denotes the bitwise XOR operator.

Input

The first line of input contains $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of testcases. Description of each testcase follows.

The first line of each testcase contains two integers $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$k$$$ $$$(1 \le k \le 10^9)$$$ — the number of nodes in the tree and the initial amount of land owned by the root.

The second line of each testcase contains $$$n-1$$$ integers $$$p_2,p_3,\cdots,p_n$$$ $$$(1 \le p_i \le n)$$$, where $$$p_i$$$ is the parent of $$$i^{th}$$$ node.

It is guaranteed that the sum of $$$n$$$ over all testcases don't exceed $$$10^5$$$.

Output

For each testcase, output the maximum possible of $$$\displaystyle\sum_{i=1}^{n} (a_i \oplus i)$$$ on a separate line.

Example
Input
3
1 5

3 4
1 1
4 9
1 1 2
Output
4
6
23
Note

For the second testcase, node $$$1$$$ can divide the land equally so that node $$$2$$$ and $$$3$$$ each recieve $$$2$$$ units of land. Note that this is the only way node $$$1$$$ can divide the land.

For the third testcase, node $$$1$$$ may give $$$5$$$ units of land to node $$$2$$$ and $$$4$$$ units of land to node $$$3$$$.