There are people in the world numbered to . The -th person has a distinct name that is a string of uppercase English letters.
Two people are friends if and only if there is some letter that appears at least once in each of their names. Any such letter does not need to be at the same position in both names. After all, friendship requires having something in common!
A friendship chain of length between person and person is a sequence of people such that , , and and are friends, for to . Note that any two people can have zero or more friendship chains between them.
For each of the given pairs of people, can you find the length of the shortest friendship chain between them? If there is no friendship chain between a pair, output .
输入格式
The first line of the input gives the number of test cases, . test cases follow. The first line of each test case contains the two integers and . The second line contains strings, which are people's names. The -th string (starting from ) is . Then, lines follow, describing the queries. The -th of these lines contains the two integers and , which are the indexes (counting starting from ) of a pair of people in the list of names.
输出格式
For each test case, output one line containing Case : , where is the test case number (starting from ) and is a list of the answers for the queries in order, separated by spaces.
In the st query, LIZZIE and KEVIN are friends (because they share the letter E in their names). So, the shortest friendship chain length is .
In the nd query, LIZZIE and BOHDAN are not friends, but have possible shortest friendship chains (either via KEVIN or LALIT). So, the shortest friendship chain length is . Note that there are other friendship chains as well, but they are longer.
In Sample Case #, there are queries:
In the st query, KICK and START are not connected by a chain of friends.
The nd query is the same as the st query. Note that queries are not guaranteed to be distinct.
