Every great day begins with a breakfast of champions, and Ms. Evans has chosen her favourite breakfast: a salad.
Ms. Evans has
- 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
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
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.
Comments