CF232C.Doe Graphs

John Doe decided that some mathematical object must be named after him. So he invented the Doe graphs. The Doe graphs are a family of undirected graphs, each of them is characterized by a single non-negative number — its order.

We'll denote a graph of order k as D(k), and we'll denote the number of vertices in the graph D(k) as |D(k)|. Then let's define the Doe graphs as follows:

• D(0) consists of a single vertex, that has number 1.
• D(1) consists of two vertices with numbers 1 and 2, connected by an edge.
• D(n) for n ≥ 2 is obtained from graphs D(n - 1) and D(n - 2). D(n - 1) and D(n - 2) are joined in one graph, at that numbers of all vertices of graph D(n - 2) increase by |D(n - 1)| (for example, vertex number 1 of graph D(n - 2) becomes vertex number 1 + |D(n - 1)|). After that two edges are added to the graph: the first one goes between vertices with numbers |D(n - 1)| and |D(n - 1)| + 1, the second one goes between vertices with numbers |D(n - 1)| + 1 and 1. Note that the definition of graph D(n) implies, that D(n) is a connected graph, its vertices are numbered from 1 to |D(n)|.

The picture shows the Doe graphs of order 1, 2, 3 and 4, from left to right.

John thinks that Doe graphs are that great because for them exists a polynomial algorithm for the search of Hamiltonian path. However, your task is to answer queries of finding the shortest-length path between the vertices a__i and b__i in the graph D(n).

A path between a pair of vertices u and v in the graph is a sequence of vertices _x_1, _x_2, ..., x__k (k > 1) such, that _x_1 = u, x__k = v, and for any i (i < k) vertices x__i and x__i + 1 are connected by a graph edge. The length of path _x_1, _x_2, ..., x__k is number (k - 1).

约翰·多伊（John Doe）认为某种数学对象必须以他的名字命名，于是他发明了“多伊图”（Doe graphs）。多伊图是一族无向图，其中每个图均由一个唯一的非负整数——其“阶”（order）——刻画。

我们将阶为 $k$ 的图记作 $D(k)$，并将图 $D(k)$ 中的顶点数记作 $|D(k)|$。于是，多伊图定义如下：

• $D(0)$ 仅包含一个编号为 $1$ 的顶点；
• $D(1)$ 包含两个编号分别为 $1$ 和 $2$ 的顶点，并由一条边相连；
• 对于 $n \geq 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$ 的多伊图。

约翰认为多伊图极为出色，是因为在其上存在一种多项式时间算法可用于寻找哈密顿路径。然而，你的任务是回答若干查询：对给定的图 $D(n)$，求顶点 $a_i$ 与 $b_i$ 之间的最短路径长度。

图中一对顶点 $u$ 与 $v$ 之间的路径是指一个顶点序列 $x_1, x_2, \dots, x_k$（其中 $k > 1$），满足 $x_1 = u$，$x_k = v$，且对任意 $i < k$，顶点 $x_i$ 与 $x_{i+1}$ 由图中的一条边相连。路径 $x_1, x_2, \dots, x_k$ 的长度定义为 $k - 1$。

The first line contains two integers t and n (1 ≤ t ≤ 105; 1 ≤ n ≤ 103) — the number of queries and the order of the given graph. The i-th of the next t lines contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ 1016, a__i ≠ b__i) — numbers of two vertices in the i-th query. It is guaranteed that a__i, b__i ≤ |D(n)|.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

第一行包含两个整数 $t$ 和 $n$（$1 \leq t \leq 10^5$；$1 \leq n \leq 10^3$）—— 分别表示查询次数和给定图的阶数。接下来的 $t$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 10^{16}$，且 $a_i \neq b_i$）—— 表示第 $i$ 次查询中的两个顶点编号。保证 $a_i, b_i \leq |D(n)|$。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

For each query print a single integer on a single line — the length of the shortest path between vertices a__i and b__i. Print the answers to the queries in the order, in which the queries are given in the input.

对于每个查询，在单独的一行上输出一个整数——顶点 $a_i$ 与 $b_i$ 之间最短路径的长度。请按照输入中查询给出的顺序输出各查询的答案。