LLCA - Largest Labeled Common Ancestor

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


Added by:Lukmanul Hakim
Date:2010-11-08
Time limit:1s
Source limit:256B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM-ICPC Indonesia National Contest 2010, Problem B

hide comments
2014-08-06 12:42:23 Rishav Goyal
@problemSetter, how hard it is to correct input files. Its just really annoying.!
I think admin must have a look at this problem.!


Last edit: 2014-08-06 12:42:37
2011-09-25 10:09:10 numerix
Justin: You are right, the input data is broken. There seem to be more or less than 3 values in at least one line and/or empty lines in between.

Lukmanul Hakim: Thanks for increasing timelimit. Seems okay now for Java; as my Pike solutions gives WA (maybe because of the reason stated above), I don't know if TL will suffice for all sets.
2011-09-25 10:09:10 hendrik
Justin: I tried to start a discussion about the quality of the input files in the forum. No one really cared. You have to live with the fact that some problemsetters dont do a good job or perhaps dont know anything else than scanf.

Last edit: 2011-06-07 23:32:30
2011-09-25 10:09:10 skeeve
Are there extra blank lines at the beginning of the input? Something like that is going on (though I got around it). I hate it when problems do stupid things like that. Is it so hard to make good, simple input files? I hate wasting time on things like this.
2011-09-25 10:09:10 numerix
The source limit isn't too strict, but the time limit is for some interpreted languages, because of long startup time of the interpreter (e.g. Pike, Java). So, please set time limit to a higher value. Thanks.

Reply : OK, time limit updated. Is it enough?

Last edit: 2011-03-02 09:55:28
2011-09-25 10:09:10 Hendra Jaya
I spent more time minimizing the source code than constructing the algorithm.
What's the point of 256B limitation? This is not codegolf...

Reply : You can find more problem with time limit and source limit like this here. This is SPOJ!

Last edit: 2011-01-06 02:09:19
2011-09-25 10:09:10 যোবায়ের
why? @Andri
2011-09-25 10:09:10 Muhammad Andri Ihsannudin
i think the problem submitter has a problem. :|
2011-09-25 10:09:10 Prahesa Kusuma Setia
NICE PROBLEM GAN! xD
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.