Rooms in Bytelandian houses are rather strange, they may or may not be exactly rectangular. But the walls of the room are aligned either vertically or horizontally to the town's XY axis. Additionally, each wall is integral in length. Thus the rooms are denoted by using the letters '-', '|', '+' and ' '. Let us denote a place occupied by one letter as cell. Here '-' specifies one unit of horizontal wall, '|' specifies one unit of vertical wall, and '+' means the wall turns in the center of the cell. For example, one of the valid rooms is the following:

+-----+ | +-------+ +--+ | | +-----+ +-------+ | | | +--+

Also if you draw a horizontal segment whose the end points are in the room, then the whole of the segment is inside of the room. And there are other constraints for the rooms, please see Notes, Some samples of valid rooms for input, and Some samples of invalid rooms for input.

How weird, but it gives a chance to lot of children to play a game together. The game starts with all children standing on corners of the room. More precisely, children stand on the nearest empty cell which is inside of the room. Each child stands in one corner, and all corners must be occupied. We only consider corners which make a 90 degree angle inside the room. Those that make 270 degree angle inside room are not considered as a corner. In the below figure, 1, 3, 4 are valid corners but 2 is not. Thus all the cells denoted by * will have one child.

1-----4 |* *+-------+ 3--2 *| |* +-----+ +-------+ | |**| +--+

Note that it is possible that the two corner has space for only one child, as shown below.

+--- |* +---

In the game, a child can swap positions with a child standing at an adjacent corner. Thus, in the below figure, child 'A' can swap place with either 'B' or 'D', and child 'D' can swap place with either 'A' or 'E'. Inside a room many swaps can be taking place simultaneously, but each swap is between 2 children only. Also while swapping positions, children should keep one hand touching the wall, which means they can move only along the walls.

+-----+ |A B+-------+ +--+ C| |D +-----+ +-------+ | |EF| +--+

Considering each child takes one second to walk to an adjacent empty cell, some pair of friends want to know the minimum time in which they can cross each other. Crossing happens when 2 children, both moving towards the corner of the other child (for swapping), meet briefly in the middle of swap. And a child can start to swap with other child only when both children stand at corners. For example, when child 'C' swaps with 'F', the swapping will be the following, and they cross with time = 4.5.

Input

First line consists of an integer N. Then N lines follow to represent the room. Children are described as capital alphabets (A-Z), to specify the child standing next to a corner. There may be several children labelled with same alphabet. In row-major order, the first child with some alphabet a is referred to as a1, the second as a2, and the 123rd as a123 and so on.

After N lines, there is a line which contains T, the number of queries. Then T lines follow each containing a pair of space separated labels (character and number) to denote the pair of friends.

Output

For each of T given pair of friends, you have to output the minimum time in which the given pair of friends can cross each other, assuming that the pair of friends play intelligently and each pair starts from the original positions. Output T real numbers (2 places after decimal), one on each line.

Constraints

5 = N = 2500
3 = length of each of N lines (to describe a room) = 2500
1 = T = 10000

Example

Input: 7 +-----+ |A B| +--+ | |C | | | |A E| +--------+ 2 A1 E1 C1 A2 Output: 6.00 1.00

Notes

• All the labels given in input are valid, that is, each label denotes one child in the room.
• All children are inside of the room.
• Children labelled by the same letter do not appear on the same horizontal line.
• The room must satisfy the condition: If you draw a horizontal segment whose the end points are in the room, then the whole of the segment is inside of the room.
• All empty cells, which are inside the room, are 4-connected, where an empty cell means a cell denoted by a space ' ' or a capital alphabet (A-Z).
• For each of wall cells '-', '|' and '+', there is at least one empty cell, which is inside of the room, lying next (horizontally, vertically or diagonally) to each other.
• For each of corner cells, there is a cell having a child in the next (diagonally) to the corner cell.
• For each of cells having children, there is a corner cell in the next (diagonally) to the cell having a child.
• There is at least one line of N lines (to describe a room), whose first character is not a space ' '.
• The last character of each of N lines (to describe a room) does not be a space ' '.

Some samples of valid rooms for input

+-----+ |A B+-------+ +--+ B| |A +-----+ +-------+ | |AB| +--+

The room described in the above figure is valid.

+-------------+ |A B| | +-----------+ | | | | | +-----------+ |C D| +-------------+

In the above figure, child 'B' can swap place with child 'D' directly.

+-+ |A++ | B++ | C++ |D E| +----+

The room described in the above figure is also valid.

Some samples of invalid rooms for input

+-----+ |A B+-------+ +--+ | |D +-----+ +-------+ | |EF| +--+

In the above figure, there are corners without children.

+-----+ +----+ |A B+--+C D| |E F| +-------------+

In the above figure, the room must satisfy the condition: If you draw a horizontal segment whose the end points are in the room, then the whole of the segment is inside of the room. And all lines start with spaces ' ', which also violates the constraints. Furthermore it also violates the constraint 5 = N.

+----+ |A B| +-++-+ E || +-++-+ |C C| +----+

In the above figure, all empty cells, which are inside the room, must be 4-connected. See the below figure, here, the empty cells (inside of the room) are denoted by *, and they are not 4-connected. And children labelled by the same letter must not appear on the same horizontal line. And child 'E' is outside of the room.

+----+ |****| +-++-+ || +-++-+ |****| +----+ +----+ |A B| | ++ |C D++ +----+

In the above figure, the right 2 cells with '+' must have adjacent empty cells.