1440: Rikka with Square Numbers
[命题人 : ]
题目描述
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 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, 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$.