I. Anas Steroids
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two strings $$$s$$$ and $$$t$$$. Initially, the current string is equal to $$$s$$$.

In one operation, you may do exactly one of the following:

  • remove a non-empty prefix of the current string;
  • remove a non-empty suffix of the current string;
  • insert a non-empty string at any position of the current string, including before the first character or after the last character.

The inserted string may be chosen arbitrarily, and its length does not matter.

Find the minimum number of operations needed to make the current string equal to $$$t$$$.

Input

The first line contains one integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of test cases.

Each of the next $$$q$$$ lines contains two strings $$$s$$$ and $$$t$$$ ($$$1 \le |s|, |t| \le 10^6$$$). The strings consist only of lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$|t|$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print one integer — the minimum number of operations needed to make $$$s$$$ equal to $$$t$$$.

Example
Input
7
abc abc
abc bc
abc ab
ac abc
abc b
abc de
ab axyb
Output
0
1
1
1
2
2
1
Note

In the first test case, the strings are already equal.

In the second test case, remove the prefix $$$\texttt{a}$$$ from $$$\texttt{abc}$$$.

In the fourth test case, insert $$$\texttt{b}$$$ between $$$\texttt{a}$$$ and $$$\texttt{c}$$$.

In the fifth test case, one operation is not enough. We can remove the prefix $$$\texttt{a}$$$ and then remove the suffix $$$\texttt{c}$$$.