Rikka with Square Numbers

Problem Description

Rikka struggles with math. Observing this, Yuta decides to help her improve by assigning some math practice tasks. Here is one such task. The task requires transforming one integer, $a$, into another, $b$, where $a \neq b$. In a single operation, Rikka can either add a positive square number to $a$, or subtract a positive square number from $a$. The goal is to convert $a$ into $b$ by executing the least number of operations. A square number is an integer that is the product of some integer with itself. For example, $1$, $4$, $9$, and $16$ are square numbers, as they are the squares of $1$, $2$, $3$, and $4$, respectively. The problem might seem complex for Rikka. Can you assist Rikka in solving this?

Input

The first line contains one integer $T$ ($1\le T\le 10^3$), indicating the number of test cases. For each test case, the only line contains two integers $a,b$ ($1\le a,b\le 10^9$, $a\neq b$).

Output

For each test case, output a single line containing one integer, indicating the minimum number of operations required.

Sample Input

2
1 4
5 1

Sample Output

2
1

Hint

Consider the first sample where Rikka can add $2^2=4$ to $a$, and then subtract $1^2=1$ from $a$. After executing two operations, $a$ becomes $4$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）