Paul Graph

All submissions for this problem are available.
Paul Graph
Robin Paul invented a series of undirected graphs ,each given a single positive number its order.He named them as Paul graphs.
A graph of order n will be denoted as P(n), and the number of vertices in the graph P(n) as P(n). Then let's define the Paul graphs as follows:
P(0) consists of a single vertex, that has number 1.
P(1) consists of two vertices with numbers 1 and 2, connected by an edge.
P(m) for m ≥ 2 is obtained from graphs P(m  1) and P(m  2). P(m  1) and P(m  2) are joined in one graph, at that numbers of all vertices of graph P(m  2) increase by P(m  1) (for example, vertex number 1 of graph P(m  2) becomes vertex number 1 + P(m  1)). After that two edges are added to the graph: the first one goes between vertices with numbers P(m  1) and P(m  1) + 1, the second one goes between vertices with numbers P(m  1) + 1 and 1. Note that the definition of graph
P(n) implies, that P(n) is a connected graph, its vertices are numbered from 1 to P(n).
View Image Here
Picture shows the paul graphs of order 1,2,3 and 4 ,from left to right
Robin thinks Paul graphs are that great because for them exists a polynomial algorithm for the search of Hamiltonian path. However, your task is to answer testcases of finding the shortestlength path between the vertices ui and vi in the graph P(m).
A path between a pair of vertices x and y in the graph is a sequence of vertices a1, a2, ..., ak (k > 1) such, that a1 = x, ak = y, and for any i (i < k) vertices ai and ai + 1 are connected by a graph edge. The length of path a1, a2, ..., ak is number (k  1).
Input:
First line has two integers t (number of test cases)and n(order of the graph).The ith of the next t lines contains two integers ui and vi  numbers of two vertices in the ith test case. It is guaranteed that ui, vi ≤ P(n).
Prefer %I64d specifier to %lld specifier to read/write 64 bit integers in C++.
Constraints :
1 ≤ t ≤ 100;
1 ≤ n ≤ 100
1 ≤ ui, vi ≤ 100000, ui ≠ vi
Output:
For each Test case print the length of the shortest path between vertices ui and vi.
Sample Test Case:
Input:
5 6
1 3
2 3
4 6
2 6
3 5
Output :
1
1
2
2
2
Author:  csaapogee 
Tags  csaapogee 
Date Added:  15032013 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 