Problem Description

You are given two strings $s$ and $t$ of length $n$, indexed from $1$.

In one operation, you may freely choose a non-decreasing integer sequence $p$ of length $n$ with values in $[1,n]$, satisfying $|p_i-i|\le 1$. Then, simultaneously, set all $s_i\gets s_{p_i}$.

Find the minimum number of operations needed to transform $s$ into $t$. If it is impossible, output $-1$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

Then for each test case, the first line contains the string $s$, and the second line contains the string $t$.

Output Format

For each test case, output one integer per line, the answer.

11
aabbccc
abbbbbc
abbac
baabc
abcbcab
abbabbb
ababbbac
abaaabcc
aab
baa
ababaabababbb
baaabaababbba
abrcadabra
aaaabbbraa
aabababababababbababaab
abababaaabababababbabbb
azusa
aaaaa
anotheruniversity
inneroceanfantasy
breakplus
bbbbbpppp

2
-1
2
2
-1
3
3
1
2
-1
4

Hint

Sample Explanation

For the first test case, we can transform $s$ into $t$ as follows:

$$\texttt{aabbccc}\to\texttt{abbbbcc}\to\texttt{abbbbbc}$$

The corresponding sequences $p$ for the two operations are $[1,3,4,4,4,5,6]$ and $[1,2,3,4,5,5,7]$.

It is impossible to do this in a single operation, so the answer is $2$.

Constraints

Let $m$ denote the size of the alphabet, that is, the strings only contain the first $m$ lowercase English letters.

$\text{Subtask}$	$n,\sum n\le$	$m\le$	Special Property	$\text{Score}$
$1$	$20$	$2$	A	$15$
$2$	$5\times 10^3$	^	None	$30$
$3$	$10^6$	$26$	B	$25$
$4$	^		None	$30$

• Special Property A: It is guaranteed that $s_i\le s_{i+1}$ and $t_i\le t_{i+1}$.

• Special Property B: It is guaranteed that $t$ only contains the character a.

For all data, it is guaranteed that $1\le T\le 5\times 10^3$, $1\le n,\sum n\le 10^6$, the strings contain only lowercase English letters, and $|s|=|t|$.