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.

\n

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

\n

Input

\n

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).

\n

Output

\n

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

\n

Example

\n

Input:\n


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

Output:\n


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. >:)

统计

递交统计

Largest Labeled Common Ancestor

信息

状态

开发

支持

还没有账户？

登录