B"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 ai and bi in the graph D(n). A path between a pair of vertices u and v in the graph is a sequence of vertices x1, x2, ..., xk (k xe2 x80 x89> xe2 x80 x891) such, that x1 xe2 x80 x89= xe2 x80 x89u, xk xe2 x80 x89= xe2 x80 x89v, and for any i (i xe2 x80 x89< xe2 x80 x89k) vertices xi and xi xe2 x80 x89+ xe2 x80 x891 are connected by a graph edge. The length of path x1, x2, ..., xk is number (k xe2 x80 x89- xe2 x80 x891). The first line contains two integers t and n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89t xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105; 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89103) -- the number of queries and the order of the given graph. The i-th of the next t lines contains two integers ai and bi (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai, xe2 x80 x89bi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x891016, ai xe2 x80 x89 xe2 x89 xa0 xe2 x80 x89bi) -- numbers of two vertices in the i-th query. It is guaranteed that ai, xe2 x80 x89bi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89|D(n)|. Please, do not use the %lld specifier to read or write 64-bit integers in xd0 xa1++. 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 ai and bi. Print the answers to the queries in the order, in which the queries are given in the input."...