Given a labeled complete k-ary tree, find the largest labeled common ancestor of two given nodes. In a complete k-ary tree, the node in the tree is labeled sequentially from the left most child to right most child, level by level. Largest labeled common ancestor of A and B is defined as the largest labeled node in the tree which has A and B as descendants. A node is a descendant of itself.

Be careful with your finger, the source limit is 256 bytes.

Input

The first line of input contains an integer T (1 <= T <= 100) the number of cases. Each cases contains three integers K, A and B (2 <= K <= 100; 1 <= A,B <= 2,000,000,000).

Output

For each test case, output in a line the largest labeled common ancestor node.

Example

Input:



4
3 42 7
2 2 6
2 1 105
4 10 13

Output:



2
1
1
3

Whitespace Explanation:
If there no input in any line, then the output for that line is a blank line :)) Sorry for inconvenience. >:)