The city of Desrugenstein is a complete mess. Looking at the map, it seems organized, since it was created in a square grid form, but there is no directions standard. Each corner says the directions you can go from there (north, south, west, east). The mayor Daniel Snake is headstrong and lazy enough to let everything as it is and forbid any change attempt. Unable to do much, the Master Spiritual Counsellor of Desrugenstein, Giordano Marfyn, asked you, Spiritual Counsellor Level XVII of Desrugenstein, lead programmer of Desrugenstein, to write a program to calculate the cost of going from a corner (x, y) to another corner (z, w), considering the messy streets.

Input

Input file contains several test cases. First line of each test case contains an integer N (1 ≤ N ≤ 10) that represents height and width of the grid that maps the city (a N x N grid). The input file ends with N = 0, and it should not be processed. Each one of the next N lines represents a street of the city, starting from the further north (N – 1) until the further south. In each one of these lines there are 4*N integers, 4 for each corner: A (north) B (south) C (west) D (east). Each one is 0 if it is not possible to go on the respective direction, or 1 if it is possible. After the city map, your program should read an integer P (1 ≤ P ≤ 100). Next P lines contain 4 integers each, x0 y0 x1 y1 representing the question: “What is the minimum cost to go from corner (x0 , y0) to corner (x1 , y1)?”. The cost to go from a corner to the nearest corner in any direction is 1.

Output

For each question, answer “Impossible” if there is no valid (respecting corners directions) path between the corners, or the minimum cost, if there is (are) path(s). Print a blank line after each test case.

Example

Input:
4
0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0
1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
5
1 3 0 3
2 3 3 0
2 3 0 0
3 1 3 2
0 3 0 0
0

Output:
1
4
7
3
Impossible