John Doe 决定某些数学对象必须以他的名字命名。所以他发明了 Doe 图。 Doe 图是一系列无向图,每个图都由一个非负数(其阶数)来表征。
我们将 k 阶图表示为 D(k),并将图 D(k) 中的顶点数表示为 |D(k)|。然后我们定义 Doe 图如下:
- D(0) 由单个顶点组成,其编号为 1。
- D(1) 由两个编号为 1 和 2 的顶点组成,通过边连接。
- n ≥ 2的D(n)由曲线D(n - 1)和D(n - 2)获得。 D(n - 1)和D(n - 2)连接在一张图中,此时图D(n - 2)的所有顶点数增加|D(n - 1)| (例如,图 D(n - 2) 的顶点编号 1 变为顶点编号 1 + |D(n - 1)|)。之后,两条边被添加到图中:第一条边位于编号为 |D(n - 1)| 的顶点之间和 |D(n - 1)| + 1,第二个位于数字为 |D(n - 1)| 的顶点之间 + 1和1。注意图D(n)的定义意味着,D(n)是一个连通图,它的顶点编号从1到|D(n)|。
图中从左到右依次为 1、2、3、4 阶 Doe 图。
John 认为 Doe 图非常好,因为对于它们而言,存在用于搜索哈密顿路径的多项式算法。然而,您的任务是回答寻找图 D(n) 中顶点 ai 和 bi 之间的最短路径的查询。
图中一对顶点 u 和 v 之间的路径是一系列顶点 x1, x2, ..., xk (k > 1),其中 x1 = u, xk = v,并且对于任何 i (i < k) 个顶点 xi 和 xi + 1 通过图边连接。路径 x1, x2, ..., xk 的长度为数字 (k - 1)。
输入
第一行包含两个整数 t 和 n (1 ≤ t ≤ 105; 1 ≤ n ≤ 103) — 查询数量和给定图的顺序。接下来 t 行的第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ 1016, ai ≠ bi) — 第 i 个查询中两个顶点的编号。保证ai,bi ≤ |D(n)|。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
对于每个查询,在一行上打印一个整数 - 顶点 ai 和 bi 之间的最短路径的长度。按顺序打印查询的答案,其中查询在输入中给出。
示例
输入 #1
10 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
输出 #1
1 1 1 2 1 2 3 1 2 1