Substring Search Indices

Given two strings ( S1 ) and ( S2 ), determine whether ( S2 ) is a substring of ( S1 ). If it is, output the starting index of the first occurrence; otherwise, output -1. Formally, if ( S1 = s_0 s_1 \dots s_{n-1} ) and ( S2 = t_0 t_1 \dots t_{m-1} ), find the smallest index ( i ) such that ( s_i s_{i+1} \dots s_{i+m-1} = t_0t_1\dots t_{m-1} ). If no such index exists, return -1. This problem requires processing multiple test cases.

inputFormat

The input is read from stdin. The first line contains an integer ( T ), the number of test cases. For each test case, there are two subsequent lines: the first line contains the string ( S1 ) and the second line contains the string ( S2 ).

outputFormat

For each test case, output on a separate line the starting index of the first occurrence of ( S2 ) in ( S1 ). If ( S2 ) is not a substring of ( S1 ), output -1.## sample

3
hello
ll
hello
world
abcde
cd

2
-1
2