题目描述

在神秘的 $\red{TeaLand }$上，茶树由一些叶子与连接叶子的树枝构成的，显然，树枝只能 连接两片叶子，所有的叶子都应该被树枝连接在一起，此外，树枝的数量正好比叶子的 数量少 $\red{1}$。

魔法少女在地上种了一片叶子，她为这片叶子编号为 $\red{1}$。之后每一天，她都会对这棵 茶树施加魔法：每片旧叶子都会长出 $\red{k }$片新的叶子以及一根连接这两片叶子的树枝，长 出的新叶子的编号从 $\red{2 }$开始依次递增，而长出新叶子的顺序则是与叶子本身的编号有关。

例如，如果 $\red{k = 2，}$那么第一天后叶子 $\red{1 }$长出了两片新叶子 $\red{\{2, 3\}，}$第二天后叶子 $\red{1}$ 长出了两片新叶子 $\red{\{4, 5\}，}$叶子 $\red{2 }$长出了 $\red{\{6, 7\}，}$叶子 $\red{3 }$长出了 $\red{\{8, 9\}}$。

很多很多天之后，叶子的数量已然无穷无尽。而魔法少女的朋友魔法少男在树上挑选 了两片叶子 $\red{a, b，}$他也从魔法少女那里问到了 $\red{k }$的大小，他想让你帮帮他，找到这两片 叶子的最近公共祖先。

我们说叶子 $\red{i }$是叶子 $\red{j }$的父亲，当且仅当叶子 $\red{j }$是从叶子 $\red{i }$上长出来的。

输入格式

第一行一个整数 $\red{T，}$表示数据组数。

每组数据仅一行三个整数 $\red{k, a, b}$。

输出格式

每组数据输出一行，表示 $\red{a, b }$的最近公共祖先。

样例

输入样例

3
2 4 6
2 6 7
3 8 10

输出样例

1
2
2

提示

对于所有测试点：$\red{1 ≤}$ $\red{T ≤}$ $\red{10^5，}$$\red{1 ≤}$ $\red{a, b ≤}$ $\red{10^{18}，}$$\red{2 ≤}$ $\red{k ≤}$ $\red{10^{18}}$。

对于 $\red{40\% }$的数据，保证 $\red{1 ≤}$ $\red{T ≤}$ $\red{10^3，}$$\red{1 ≤}$ $\red{a, b ≤}$ $\red{100}$。

对于另外 $\red{10\% }$的数据，保证 $\red{k = 1145141919810}$。

对于另外 $\red{20\% }$的数据，保证 $\red{1 ≤}$ $\red{T ≤}$ $\red{10^4}$。