P4975 God of Nasty Problems TM Diamond Tree - ①

The image for this problem may be large, so please wait patiently for it to load. What? What is a diamond tree? Alright, this is a very simple graph (not actually a tree, but it looks a lot like one) that a newbie made for fun. It looks like this.  (Alright, the picture is a bit large (and empty).)

Now you are given an infinitely large diamond tree (it is not only as big as the picture above; it continues downward). Then there are $T$ queries. Each query gives $u$ and $v$. Find the length of the shortest path between these two nodes.

The first line contains a positive integer $T$. The next $T$ lines each contain two positive integers, representing the two nodes in the query.

Output $T$ lines. Each line contains an integer representing the answer to the corresponding query.

${\rm Subtask\ 1(10\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 100$. ${\rm Subtask\ 2(20\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^3$. ${\rm Subtask\ 3(30\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^5$. ${\rm Subtask\ 4(40\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^{18}$. Translated by ChatGPT 5