问题 J: 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 6= 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 ≤ T ≤ 103 ), indicating the number of test cases. For each test case, the only line contains two integers a, b (1 ≤ a, b ≤ 109 , a 6= b).

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

2
1 4
5 1

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.