This problem was created by Clive Fraser (aka CSFPython).
When a village became too large for its inhabitants, two new villages were created close to the original village. Although the villages had special names it will be convenient to refer to the original village as village 1 and to the two new villages as village 2 and village 3. Roads were made from village 1 to village 2 and from village 1 to village 3. There was no need for a road between villages 2 and 3 because the people could simply travel via village 1.
As the population increased two more villages (4 and 5) were built close to village 2 and joined to it by roads. Later still, villages 6 and 7 were built near to village 3 and joined to it by roads.
By this time the local headman of the original village had become the king of the whole region. He liked the pattern that was emerging with new villages and decided to keep it. Whenever new villages were needed he would take the first village (smallest number) that had not yet been expanded into the neighbouring countryside and would create two new villages joined to it by roads. These villages would be given the next two numbers that had not yet been used. All the villages would have local names but the king insisted that the villages were also known by their numbers. This would be particularly useful for the new postal system that he was hoping to introduce later!
So the next phase of expansion had villages 8 and 9 joined to village 4, villages 10 and 11 joined to village 5 and so on. Although no village had more than 3 roads leading from it, journeys between villages were still reasonably short. For example a journey from village 9 to village 3 would go through villages 4, 2 and 1. A journey from village 11 to village 4 would go through villages 5 and 2.
The problem is to calculate the number of villages that you would need to travel through in order to go
between a specified pair of villages by the shortest possible route. The number will include the villages at
the start and end of the route. If we use J(v1,v2) to represent the number of villages in the journey
between villages v1 and v2 (inclusive), then from the examples above, J(9,3) = 5 and J(11,4) = 4.
Similarly J(1,2) = 2 and J(3,3) = 1.
Input data:
First line gives number of "test-cases".
Each of the following lines contains one such test - pair of number,
representing villages for start and finish of the route.
Answer Just contains lengths of routes, separated with spaces.
Example
input:
4
26 84
89 85
912 107
102649 493550
11 9 14 33