Word graphs

Suppose you are given a dictionary of English words. For simplicity, we will only consider words of the same length. We can define a distance function between words by counting the number of places in which they differ (this is known as Hamming distance). Suppose we make a graph with words as nodes and add edges between any 2 words that have Hamming distance 1. In other words, there is an edge between two words if one can be obtained from the other by changing exactly one character. We can then study different properties of the graph. For example, given two words, what is the shortest path between them (in terms of number of edges)? You should be able to see that the Hamming distance is a lower bound on the path length, but they need not be equal.

E.g. consider the words trend and triad. The Hamming distance is 2 and there is a path of length 2 as well: trend,tread,triad. On the other hand, consider a shortest path (of length 10) from there to which: there, where, whore, whorl, whirl, whirs, whips, whipt, whist, whish, which.

In this question you will be given an English dictionary with all 5 letter words, one word per line, but not in lexicographic order. Then you will be given a set of node pairs, each with 2 numbers and you will print the shortest distances between those node pairs.

Input

The first line of input contains a single integer n (n < 6000). Each of the next n lines contains a five letter word. Considering these numbered as 1..n, the next few lines each contain a pair of node numbers i, j (both i,j are between 1 and n, inclusive) The last line of input contains the pair 0 0. Do not process this line.

Output

For each pair i,j, (other than the 0 0 in the last line), print out the shortest path length between nodes i,j in the graph you created. If there is no path, print the string "Not connected".

Sample Input

6
aaaaa
aaaab
aaaac
ccccd
cccce
aaabb
1 3
1 4
5 4
1 6
0 0

Sample Output

1
Not connected
1
2