问题 E: World Fragments II

This problem is different from World Fragments I and World Fragments III. Please read the statements carefully.
There are $q$ queries for you to answer. Only when you have answered the previous queries can you get the next query.
For each query, you are given two non-negative decimal integers $x$ and $y$ without leading zeros. You can apply the following operation to $x$ any number of times (possibly zero):

1. Choose a digit $b$ in $x$.
   
2. Let either $x\leftarrow x+b$ or $x\leftarrow x-b$.
   

For example, when x=(616)10x = (616)_{10}x=(616)10 you can choose the digit b=(1)10b=(1)_{10}b=(1)10 in (61‾6)10(6\underline{1}6)_{10}(616)10, then let x←x−b=(616)10−(1)10=(615)10x \gets x - b = (616)_{10} - (1)_{10} = (615)_{10}x←x−b=(616)10−(1)10=(615)10.
Find out the least number of operations needed to turn $x$ into $y$. Print $-1$ if it is impossible to turn $x$ into $y$.

The first line contains a positive integer $T$ (1≤T≤3×1051\leq T\leq 3\times 10^51≤T≤3×105) — the number of queries.
Each query consists of a line that contains two integers x′,y′x', y'x′,y′. Let the answer of the previous query be $\mathrm{lastans}$. Specifically, $\mathrm{lastans}$ is considered to be $0$ for the first query. The decimal integers x,yx, yx,y in the given query are shown as below, where $\oplus$ denotes the bitwise exclusive OR operation.
x=x′⊕(lastans+1),y=y′⊕(lastans+1)x = x' \oplus (\mathop{lastans} + 1), \; y = y' \oplus (\mathop{lastans} + 1)x=x′⊕(lastans+1),y=y′⊕(lastans+1)
It is guaranteed that 0≤x,y≤3×1050\leq x, y\leq 3\times 10^50≤x,y≤3×105 holds for each query.

	For each query, print a decimal integer in a single line, denoting the answer. If it is impossible to turn $x$ into $y$, print $-1$.

6
0 8
17 16
16 17
1 5
12 0
4 7

6
6
2
-1
3
-1

	The actual queries and the operations in their optimal ways are shown as followings:




	
	

		
		
			$x=1,y=9$, optimal $6$ operations: 1‾→2‾→4‾→8‾→16‾→1‾0→9\underline{1} \to \underline{2} \to \underline {4} \to \underline{8} \to 1\underline{6} \to \underline{1}0 \to 91→2→4→8→16→10→9.
		


	

	

		
		
			$x=22,y=23$, optimal $6$ operations: 2‾2→24‾→2‾8→3‾0→2‾7→2‾5→23\underline{2}2 \to 2\underline{4} \to \underline{2}8 \to \underline{3}0 \to \underline{2}7 \to \underline{2}5 \to 2322→24→28→30→27→25→23.
		


	

	

		
		
			$x=23,y=22$, optimal $2$ operations: 23‾→2‾0→222\underline{3} \to \underline{2}0 \to 2223→20→22.
		


	

	

		
		
			$x=2,y=6$, impossible.
		


	

	

		
		
			$x=12,y=0$, optimal $3$ operations: 12‾→1‾0→9‾→01\underline{2} \to \underline{1}0 \to \underline{9} \to 012→10→9→0.
		


	

	

		
		
			$x=0,y=3$, impossible.