CF2242D Two Digit Strings

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.

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 $ .

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.

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 $ .