I. Hall of Faces
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The members of the Faceless Men possess the unique capability to physically change their faces, shapeshifting so that they appears as an entirely new person. Their headquarters are located in the House of Black and White, where the Hall of Faces exists.

Inside Hall of Faces there exists rows of skinned faces belonging to deceased individuals. Those faces are displayed and labeled according to their defining characteristics (a label example could be: fatty , silver-haired , one-eyed etc). Note that it's possible for the hall of faces to have multiple faces with the same defining characteristic (thus same label).

After accepting a certain mission Jaqen H'ghar went to the hall of faces to get the corresponding face for his new persona

To find the face he wanted, Jaqen H'ghar must first return the face he currently uses to his position in the hall of faces then pick a new face based on the defining characteristic he need for completing the job.

For the purpose of this problem, let's assume that the Hall of Faces is designed in a circular fashion and that all faces are placed in a single row on the wall. Can you determine the minimum number of faces Jaqen H'ghar must inspect before finding the face he wants?

If the face desired by Jaqen H'ghar is not present inside the hall of face output -1.

Note: Jaqen view faces in order, going either in the clockwise or counter clockwise direction before finding the one he wants

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ the number of faces in the hall of faces along with string that represent the label of the face that Jaqen want.

Each face is represented by a corresponding label (different faces may have the same label). different label are seperated by a white space. Among the different label you are guaranteed to have only one having as value "Jaqen". This indicate the position of the face that Jaqen is currently using.

The sum of number of characters over all test case is guaranteed to be less than $$$10^6$$$ and the length of each label is guaranteed to be less than 20 character long.

Output

After returning the face he is currently using to his position, output the minimum number of faces Jaqen H'ghar has to consider before finding the face he wants.

Example
Input
3
5 one-eyed
red-haired Jaqen silver-haired one-eyed red-haired
6 brown-eyed
brown-eyed brown-eyed silver-haired one-eyed Jaqen long-nose
3 thick-eyebrows
Jaqen brown-eyed long-nose
Output
2
2
-1