You have 2m dots on X-axis. The dots are colored in m different colors such that there are exactly 2 dots of each color. The dots are placed at the coordinates (1,0), (2,0), ..., (2m, 0).

 

Your task is to draw a path for each color that joins the two dots of that color. Each path should be composed of vertical or horizontal line segments between grid points. No two paths can intersect or touch each other. No path may cross the y=0 line. Each path can only touch the y=0 line at the position of the two marbles it is connecting, so the first and last line segment of each path must be vertical.

 

Given an arrangement of dots, return the minimum height of a solution, or return -1 if no solution exists.

 

The height is defined as the difference between the highest and lowest Y-coordinates of the paths used.

 

An example:

green green yellow red yellow red
One solution would be: __________ | | green ---- green yellow red yellow red |____________|

The minimum height is 2 in this case.

 

Input

 

The first line of input gives the number of test cases, T, followed by the cases.
The first line of each case contains m, the number of different colors for the marbles.
The next line contains a string of 2m words separated by spaces which correspond to the colors of the
dots, in order from left to right.

 

Output

 

For each test case, output the line containing the height of any optimal solution, or -1 if no solution exists.

 

Constraints

1

Example

Input: 4 3 orange orange red yellow red yellow 3 black blue white black blue white 3 brown green yellow green yellow brown 3 pink pink blue blue yellow yellow Output: 2 -1 3 1