Word graphs revisited

Suppose you are given a dictionary of 5-letter English words. We can define a distance function (different from that used in the previous contest) between words using the Hamming distance (recall that this is defined to be the number of places in which two words differ). 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. Further we can add weights to edges by using the distance between the characters(by which the words differ) in the English alphabet. For example the edge between words "stone" and "store" would have weight 4, because the distance between n and r is 4 (n->o->p->q->r).

We can then study shortest paths in this weighted graph. For example, given two words, what is the shortest path between them (shortest here means "least cost")?

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
aaaba
ccccd
cccce
aaabb
1 6
2 3
1 4
0 0

Sample Output

2
2
Not connected