Minimum Circular Shifts

You are given two strings S and T of equal length. Your task is to determine the minimum number of circular shift operations needed to transform string S into string T. A circular shift is defined as rotating the characters of the string either to the left or right by one position. Formally, if we denote a left circular shift by one position as transforming a string \( S = s_0s_1 \dots s_{n-1} \) into \( s_1s_2 \dots s_{n-1}s_0 \), then you need to compute the minimum number of such operations (taking the smaller count between left and right shifts) to obtain T from S if possible. If it is impossible to transform S into T using circular shifts, output -1.

In mathematical terms, you are to find the minimum non-negative integer \( k \) such that either:

[ T = \text{rotate}(S, k) \quad \text{or} \quad T = \text{rotate}(S, n - k), ]

where \( n \) is the length of the string, and \( \text{rotate}(S, k) \) denotes the string obtained after k circular left shifts.

inputFormat

The first line of input contains a single integer N indicating the number of test cases. Each of the following N lines contains two space-separated strings S and T, both of equal length.

Example:

6
abcde deabc
hello ohell
a a
abcd bcda
abcd dabc
abcd cdab

outputFormat

For each test case, output a single line with the minimum number of circular shift operations needed to transform S into T. If it is not possible, output -1.

Example:

2
1
0
1
1
2

## sample

4
abcde deabc
hello ohell
a a
abcd bcda

2
1
0
1

</p>