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:
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).
The first line contains two integers t and n (1 ≤ t ≤ 10^{5}; 1 ≤ n ≤ 10^{3}) — 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} ≤ 10^{16}, 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.
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.
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
2
1
2
3
1
2
1
Name |
---|