Background

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

Problem Description

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.

Input Format

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 Format

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

3
1 1
5 10
6 7

0
7
9

Hint

${\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