C. Portals
time limit per test
1 second
memory limit per test
256 megabytes
input
portals.in
output
standard output

Mr. Light is making a video game that can be represented as a ninja moving around a grid of 1 row and n columns.

Each cell is one of 5 types:

  1. '.'; an empty cell. A ninja in this cell can move to the cell directly to its left or its right (if it exists and it is not blocked).
  2. '#'; a blocked cell. A ninja cannot enter this cell.
  3. 'o'; a portal. A ninja in this cell can jump to any other cell of the same type, or to the cell directly to its left or its right (if it exists and it is not blocked).
  4. 's'; starting cell of the ninja. There is exactly one cell of this type in the grid.
  5. 'e'; ending cell of the ninja. There is exactly one cell of this type in the grid.

The starting and ending cells are also empty cells, so the ninja can move from and to them in the same way.

Mr. Light wants to change a minimum number of empty cells to blocked cells (type 1 to type 2) such that there is no possible way for the ninja to get from the starting cell to the ending cell. Cells of type 2, 3, 4, and 5 cannot be changed.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 27000), the number of test cases.

The first of each test case is n (2 ≤ n ≤ 2 × 105), the number of columns in the grid.

The next line contains n characters, where each character is one of the following: '.', '#', 'o', 's', or 'e'. It is guaranteed that there is exactly one 's' and one 'e' in the grid.

The sum of n over all test cases doesn't exceed 2 × 106.

Output

For each test case, output the minimum number of empty cells that need to be blocked to make it impossible for the ninja to reach the ending cell. If there's no way to achieve that, print  - 1, on a single line.

Example
Input
3
9
o.s...e.o
11
#..soe..#..
3
s#e
Output
2
-1
0