|Codeforces Round #144 (Div. 1)|
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 ≤ 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.
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.