# Problem D

Traveling Salesman

## Input

Each test case consists of a line containing $c$, the number of countries ($4 \le c \le 6000$), followed by $c$ lines containing the integers $n\; x_1\; y_1\; z_1\; \dots \; x_ n\; y_ n\; z_ n$, describing (in order) the $n$ corners of a closed polygon ($3 \le n \le 20$). Then follows a line with one integer $m$ $(0 < m \leq 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^7 \leq x,y,z \leq 10^7$ 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 1 | Sample Output 1 |
---|---|

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 |
2 1 |