D. Hard Work
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string of n characters

You need to find the length of the shortest substring that contains all letters 'h', 'a', 'r', 'd', 'w', 'o', 'r', 'k' in any order

Note that you the substring needs to contain two 'r'

If no substring exists which contains all these letters, print -1

Input

First line consists of a single integer t, number of tests ($$$1 \leq t \leq 1000$$$)

First line of each test consists of single integer n, size of string ($$$1 \leq n \leq 10^5$$$)

Second line of each test consists of the word

Output

For each test, print the length of the shortest substring that contains the letters 'h', 'a', 'r', 'd', 'w', 'o', 'r', 'k'

Example
Input
9
8
hardwork
7
hardwok
15
rwkrhhkkaokdrrw
15
kdrrwdoaahdoadw
15
dwororaohrkaaor
15
hhawdkowdhwarak
15
rarraakhaorkadh
15
rkrwawoarkrkdhk
15
woaodkdaoadrwdw
Output
8
-1
10
10
11
-1
-1
9
-1