F-World Fragments II_2026牛客五一集训派对day1

时间限制：C/C++/Rust/Pascal 9秒，其他语言18秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

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):

Choose a digit $b$ in $x$ .
Let either $x \gets x + b$ or $x \gets x - b$ .

For example, when $x = (616)_{10}$ you can choose the digit $b=(1)_{10}$ in $(6\underline{1}6)_{10}$ , then let $x \gets 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\leq T\leq 3\times 10^5$ ) — the number of queries.

Each query consists of a line that contains two integers $x', y'$ . Let the answer of the previous query be $\mathop{lastans}$ . Specifically, $\mathop{lastans}$ is considered to be $0$ for the first query. The decimal integers $x, y$ in the given query are shown as below, where $\oplus$ denotes the bitwise exclusive OR operation.

$x = x' \oplus (\mathop{lastans} + 1), \; y = y' \oplus (\mathop{lastans} + 1)$

It is guaranteed that $0\leq x, y\leq 3\times 10^5$ 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$ .

示例1

输入

复制

输出

复制

备注:

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

$x = 1,\; y = 9$ , optimal $6$ operations: $\underline{1} \to \underline{2} \to \underline {4} \to \underline{8} \to 1\underline{6} \to \underline{1}0 \to 9$ .
$x = 22,\; y = 23$ , optimal $6$ operations: $\underline{2}2 \to 2\underline{4} \to \underline{2}8 \to \underline{3}0 \to \underline{2}7 \to \underline{2}5 \to 23$ .
$x = 23,\; y = 22$ , optimal $2$ operations: $2\underline{3} \to \underline{2}0 \to 22$ .
$x = 2,\; y = 6$ , impossible.
$x = 12,\; y = 0$ , optimal $3$ operations: $1\underline{2} \to \underline{1}0 \to \underline{9} \to 0$ .
$x = 0,\; y = 3$ , impossible.