Shortest Path in the Infinite Diamond Tree

You are given an infinite diamond tree. The tree is actually a complete binary tree (often displayed in a rotated, diamond-like form), where each node is labeled with a positive integer. The root is labeled 1. For any node with label i (where i > 1), its parent is &lfloor i/2 &rfloor. In other words, for a node i its children are 2*i and 2*i+1.

You are given T queries. In each query, you are given two nodes u and v. You are to determine the length of the shortest path between these two nodes in the tree.

The shortest path length between two nodes in a tree is defined as the sum of their distances from their lowest common ancestor (LCA). Formally, if depth(u) is the number of edges from the root to node u and LCA(u,v) is the lowest common ancestor of u and v with depth depth(LCA(u,v)), then the distance is:

\( \text{distance}(u,v)=depth(u)+depth(v)-2\times depth(LCA(u,v)) \)

You can compute the depth of a node i as \(\lfloor \log_2(i) \rfloor\).

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 10⁵), the number of queries. Each of the following T lines contains two space-separated positive integers u and v representing the nodes to query.

outputFormat

For each query, output on a new line a single integer representing the length of the shortest path between node u and node v.

sample

3
1 2
2 3
4 3

1
2
3