图片被删除,或者路径改变
问题1440--Rikka with Square Numbers

1440: Rikka with Square Numbers

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

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?

输入

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

输出

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

样例输入 Copy

2
1 4
5 1

样例输出 Copy

2
1

提示

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