Harry has found Tom Riddle's diary and now must acquire a Basilisk fang to destroy it. But first he wants to know how much dark energy this Horcrux holds. He also wants to check if it is the real horcrux, since acquiring the fang would be a dangerous task.

The diary's contents are represented by a string S.
The amount of Dark Energy in the diary is equal to the minimum length of a substring of S, in which the given string P occurs as a subsequence.
If P does not occur as a subsequence in any of the substrings of S, the diary is a fake.

Definitions: Substring , Subsequence

Input
The first line contains an integer T, the number of testcases.
Then each testcase is described by 2 lines - strings S in first line and string P in the next line.

Output
Print the Dark Energy value of each testcase in a new line.
If the diary is a fake, print -1 instead.

Constraints
1 <= T <= 20
1 <= |S| <= 100000
1 <= |P| <= 100