Book Hand Delivery

John is part of a large reading group where members share their books with each other. This group never meets physically so they resort to sending the books by mail. The problem is that this solution is expensive and often books get lost.

So, when John discovered most members shared some activities together, he came up with an ingenious plan. John’s idea was to deliver the books by hand, from one member to the other, until they reached their destination.

Another special thing about this group is that their schedule is always the same, week after week. John also noticed that each member only has one activity per day where they may meet another member. At this point you might be thinking that their lives are really monotonous and tedious. They are part of a reading group, what did you expect?

The following table shows an example of a possible timetable for the group.

In this case, if John wants to deliver a book to Robert he can start by giving it to Mary when they both go pick up their kids at school. Mary can then deliver it to Oliver the next day. In two days Oliver can deliver the book to Carl and he can give it to Peter four days later when they meet at the bar. Three days after that Peter can give the book to Ashley and it will take another five days for the book to get into Megan’s hands the next Tuesday. Megan can then deliver it to Emely on Friday, three days later, and the next day the book will finally reach Robert. This means it would take 19 days for the book to get from John to Robert (0 + 1 + 2 + 4 + 3 + 5 + 3 + 1). The next table depicts this plan.

Task

Your task is to write a program that, given the group’s timetable, computes the number of days necessary to take a book from one given person to another given person. The time starts counting on the first day the book changes hands.

Input

The first line of the input will contain a single integer (P) representing the number of persons in the group.

The next P lines will contain each person’s schedule represented by 7 characters, separated with spaces, from ‘A’ to ‘Z’ or the character ‘-’ if that person has no recorded activities on that day. The individual characters on the line are separated by single spaces.

This line will be followed by another integer (Q) representing the number of questions.

The next Q lines will each contain two different integers (S and D) representing a question: what is the minimum number of days necessary to get a book from the source (S) to the destination (D)? The first person will be refered to as person 0 (zero) and the last one will be person P−1.

Output

The output will contain Q lines, one for each question, containing either one integer representing the number of days it would take for the book to get from the source to the destination or the word ‘impossible’ if there is no way to get it there.

Constraints

2 <= P <= 1000
1 <= Q <= 20
0 <= S, D <= P − 1
S ≠ D

Input example 1

10
S - - - - - -
S S - - - - -
- S - S - - -
B - S S - - -
B - - - S - -
B - - B S - -
- B - B - - -
- B - - B - -
- - - - B S -
- - - - - S -
2
0 9
2 8

Output example 1

19
15

Input example 2

4
X - X R - A -
X K - R - Z -
X K - - - Z -
- - Y X - - -
2
0 2
1 3

Output example 2

0
impossible

This document was translated from L^AT_EX by H^EV^EA.