Write a program to search for a substring (pattern) in a longer string (text) using brute-force string matching algorithm.

Input

Input begins with t (1 ≤ t ≤ 100) of number of test-cases in the first line and the test-cases in the following lines. Each test-case begins with a text (1 ≤ length of the text ≤ 1,000,000) in a single line and the pattern (1 ≤ length of the pattern ≤ 1,000,000) to be searched in a new line. The text and pattern could have spaces as characters.

Output

For each test-case, print the index (0 ≤ index < length of the text) of the beginning the pattern in the text in a new line. Print ‘-1’ if the substring is not found in the text.

Example

Input:
2
Discrete Mathematics and Logic is a prerequisite for Design and Analysis of Algorithms.
and
Discrete Mathematics and Logic is a prerequisite for Design and Analysis of Algorithms.
Logic and

Output:
21
-1