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) $ .

The first line contains two integers $ t $ and $ n $ ( $ 1

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.