Given two strings s1 and s2, find the index of the first occurrence of s2 in s1 as a substring.
If no such occurence exists, return -1.

This problem is also known as finding needle in a haystack.
Use the Rabin-Karp algorithm to solve this problem.

Example 1

s1: “helloworld”
s2: “low”
Answer: 3

Example 2

s1: “workattech”
s2: “technology”
Answer: -1

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has two lines:

• A string “s1”.
• A string “s2”.

Output Format

For each test case, the output has a line with the value ‘index’. If s2 is present in s1, index is the the index of the first occurence, otherwise -1.

Sample Input

3
competitive
pet
roundandround
round
callofduty
fall

Expected Output

3
0
-1

Constraint

1 <= T <= 50
1 <= s1.size, s2.size <= 105
All characters in s1 and s2 are lowercase English alphabets.