菊花图是从一个点向所有点连边的树。

CZY不满足于这个简单的定义，于是他给了一个更高级的定义：

给定参数k，定义0阶菊花图为只有一个根节点的树，n阶($n\ge 1$)菊花图为一个根节点下面有k个孩子，每个孩子都是n-1阶菊花图。

每个点的编号是这样的：从根开始，按照BFS的顺序从1开始对每个点编号。

LK造了一个$10^{18}$阶菊花图，由于这个图太大了，计算两个点的LCA成了一件难事，现在他给了一些询问，每组询问形如u,v表示计算u和v的LCA。

由于图太大了，LK一个询问都不会，于是他把这些询问丢给了你，请你帮他解决，并且承诺如果你帮他算出来就给你一定的分数作为奖励。

输入格式

第一行两个数T,k，T表示有T组询问，菊花图的参数为k。

接下来T行，每行两个数u,v表示计算u和v的LCA。

输出格式

T行，每行一个数lca表示u和v的LCA。

样例输入输出

样例输入

3 2
1 4
4 5
3 8

样例输出

1
2
1

数据范围

由于某些原因，本题采用捆绑测试。

设对于所有询问,$u,v\le n$。

子任务0：1分，$T=0$。

子任务1：29分，$T\le 10,n\le 10000$

子任务2：30分，$T\le 100000,n\le 1000000$。

子任务3：40分，$T\le 100000,n\le 10^{15}$。

对于$100\%$的数据，k为正整数且$k\le 100$。