You are given two strings $$$a$$$ and $$$b$$$, consisting only of digits. In one operation, you can choose two adjacent characters in either of these two strings and replace them with their sum modulo $$$10$$$. For example, from the string $$$57246$$$ you can obtain the following strings in one operation:

$$$\mathbf{57}246 \rightarrow 2246$$$;
$$$5\mathbf{72}46 \rightarrow 5946$$$;
$$$57\mathbf{24}6 \rightarrow 5766$$$;
$$$572\mathbf{46} \rightarrow 5720$$$;

Note that after such an operation, the length of the string always decreases by exactly $$$1$$$.

You can perform any number of such operations (even zero). You have to make these strings equal ($$$|a| = |b|$$$ and $$$a_i = b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$|a|$$$). Calculate the maximum possible length of the resulting equal strings.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^3$$$) — the number of test cases.

The first line of each test case contains a string $$$a$$$ ($$$1 \le |a| \le 5 \cdot 10^3$$$), consisting only of digits.

The second line of each test case contains a string $$$b$$$ ($$$1 \le |b| \le 5 \cdot 10^3$$$), consisting only of digits.

Additional constraint on the input: $$$\sum (|a| + |b|) $$$ across all test cases does not exceed $$$10^4$$$.

Output

For each test case, print one integer — the maximum possible length of the resulting equal strings. If you can't make the strings equal, print -1.

Note

In the first example from the statement, the maximum length you can obtain is 2:

$$$\mathbf{51}47 \rightarrow 6\mathbf{47} \rightarrow 61$$$;
$$$\mathbf{44}441 \rightarrow \mathbf{84}41 \rightarrow \mathbf{24}1 \rightarrow 61$$$.

In the second example from the statement, you can't make strings $$$a$$$ and $$$b$$$ equal, so the answer is -1.

In the third example from the statement, the maximum length you can obtain is 5:

$$$1234\mathbf{50} \rightarrow 12345$$$;
$$$\mathbf{01}2345 \rightarrow 12345$$$.

Two Digit Strings

Examples