3033 -- Traveling Salesman

Language:

Traveling Salesman

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 453		Accepted: 170

Description

Long before the days of international trade treaties, a salesman would need to pay taxes at every border crossed. So your task is to find the minimum number of borders that need to be crossed when traveling between two countries. We model the surface of Earth as a set of polygons in three dimensions forming a closed convex 3D shape, where each polygon corresponds to one country. You are not allowed to cross at points where more than two countries meet.

Input

Each test case consists of a line containing c, the number of countries (4 ≤ c ≤ 6000), followed by c lines containing the integers n x₁ y₁ z₁ … x_n y_n z_n, describing (in order) the n corners of a closed polygon (3 ≤ n ≤ 20). Then follows a line with one integer m (0 < m ≤ 50), and then m lines with queries c_a c_b, where c_a and c_b are country numbers (starting with 1). No point will be on the line between two connected points, and −10⁶ ≤ x, y, z ≤ 10⁶ for all points. No two non-adjacent edges of a country share a common point. The input is terminated by a case where c = 0, which should not be processed.

Output

For each query, output the number of borders you must cross to go from c_a to c_b.

Sample Input

6
4 0 0 0 0 0 1 0 1 1 0 1 0
4 1 0 0 1 0 1 1 1 1 1 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 1 0 1 1 0 1 1 1 0 1 1
4 0 0 0 0 1 0 1 1 0 1 0 0
4 0 0 1 0 1 1 1 1 1 1 0 1
2
1 2
1 3
0

Sample Output

2
1

Source

Nordic 2006