Mr. Toluene is working on a full binary tree. The root is labeled 1. For any node labeled $x$, its left child is labeled $2x$ and its right child is labeled $2x+1$. Given two nodes $a$ and $b$ in this tree, you need to answer two types of questions:

1. When $c=1$, find the minimum sum of node labels on a simple path between node $a$ and node $b$.
2. When $c=2$, find the number of simple paths in this full binary tree that have the same sum of node labels as the minimum path between $a$ and $b$, excluding the path from $a$ to $b$ itself.

A simple path is a path where no vertex is repeated.

Input

The first line contains a single integer $T$, representing the number of test cases. Each of the next $T$ lines contains four positive integers $d, a, b, c$. Here, $d$ is the depth of the full binary tree, $a$ and $b$ are two nodes in the tree, and $c$ is the type of question.

Output

For each test case, output a single line containing a positive integer representing the answer to Mr. Toluene's question.

Examples

Input 1

8
3 1 1 1
3 1 1 2
3 1 2 1
3 1 2 2
3 2 4 1
3 2 4 2
3 1 5 1
3 1 5 2

Output 1

1
0
3
1
6
2
8
0

Note

For a full binary tree of depth 3, the nodes are 1, 2, 3, 4, 5, 6, 7. The path sum from node 1 to 1 is 1, and there are no other paths with a sum of 1. The path sum from node 1 to 2 is $1+2=3$. There exists a path 3-3 with a sum of 3. The path sum from node 2 to 4 is $2+4=6$. There exist paths 2-1-3 and 6-6 with a sum of 6. The path sum from node 1 to 5 is $1+2+5=8$. There exists a path 8-8 with a sum of 8, but node 8 has a depth of 4, which does not satisfy the condition.

Constraints

• For 20% of the data, only $c=1$ occurs.
• For 20% of the data, $d \le 10$.
• For 30% of the data, $d \le 20$.
• For 40% of the data, $d \le 25$.
• For 50% of the data, $d \le 30$.
• For 100% of the data, $d \le 50$.