Every great day begins with a breakfast of champions, and Ms. Evans has chosen her favourite breakfast: a salad.

Ms. Evans has ~N~ ~(1 \le N \le 100)~ bowls, each containing a salad ingredient. There are 26 types of ingredients:

• Anchovies
• Black pepper
• Croutons
• Dates
• Eggs
• Feta cheese
• Garlic
• Horse meat
• Iceberg lettuce
• Juniper berries
• Kale
• Lemon juice
• Mangoes
• Nectarines
• Olive oil
• Parmesan cheese
• Quinoa
• Romaine lettuce
• Sesame seeds
• Tomatoes
• Unsweetened mayonnaise
• Vanilla
• Walnuts
• X-tra strength butter
• Yam
• Zucchini

Ms. Evans really likes Caesar salad, and as everyone knows, Caesar salad has only 8 ingredients:

• Anchovies
• Black pepper
• Croutons
• Eggs
• Garlic
• Lemon juice
• Olive oil
• Romaine lettuce

Ms. Evans wants to put all her bowls together and make a Caesar salad, but she doesn't want any incorrect ingredients to be included. She will be satisfied if all of the ingredients in her bowls are Caesar salad ingredients. Note that it's OK if some of the ingredients aren't present: a combination of olive oil and black pepper would still leave Ms. Evans satisfied.

These bowls are no ordinary bowls: Ms. Evans has a big red button, and when she presses it, the ~i^\text{th}~ bowl shifts ~s_i~ times ~(1 \le s_i \le 10)~. When a bowl shifts, its ingredient becomes the next ingredient in the list: vanilla becomes walnut, garlic becomes horse meat, and zucchini goes all the way back to the start and becomes anchovies.

Ms. Evans wants to know the minimum number of button presses necessary to make all her ingredients Caesar salad ingredients. Can you help her?

Input Specification

There will be ~T~ ~(1 \le T \le 100)~ test cases. The first line of input will contain ~T~. ~T~ lines will follow, each describing one test case: first the integer ~N~, then a string of ~N~ upper-case letters representing the ingredient in each bowl (each ingredient is represented by its first letter), then each value of ~s_i~ in order.

Output Specification

For each test case, output a single line containing the answer to that test case. If it is impossible to satisfy the conditions no matter how many times Ms. Evans presses the button, output -1.

Sample Input

3
2 CM 2 1
4 ABCD 1 1 1 1
3 ABC 10 5 4

Sample Output

2
-1
0

Explanation

In the first test case, the bowls contain croutons and mangoes. If she presses the button twice, the first bowl will contain garlic and the second bowl will contain olive oil. This is the minimum number of button presses.