Згідно діючих міжнародних торгових договорів, комівояжер повинен заплатити подат на кожному кордоні, який він перетинає. Тому ваше завдання полягає у пошуці мінимального числа кордонів, які потрібно перетнути під час подорожі між двома країнами. Ми маємо модель поверхні Землі у вигліді набору полігонів у трьохх вимірах, які утворюють замкнуту опуклу 3D-форму, де кожен полігон відповідає одній країні. Ви не можете перетинати кордон у точках, де зустрічаються більше двох країн.
Вхідні дані Кожен тест складається з рядка, який містить кількість країн c (4 ≤ c ≤ 6000 ), а потім йде c рядків, які містять цілі числа n x_1 y_1 z_1 ... x_n y_n z_n, що описують (по порядку) n кутів замкнутого многокутника (3 ≤ n ≤ 20). Далі йде рядок з одним цілим числом m (0 < m ≤ 50), за яким йде m рядків запитів c_a c_b, де c_a та c_b номери країн (країни пронумеровано починаючи з 1 ). Немає точок, які знаходяться на лінії, яка з'єднує дві інші точки, і −10^6 ≤ x, y, z ≤ 10^6 для усіх точок. Немає двох несуміжних ребер країни, які мають спільнк точку. Вхідні дані завершує випадок, коли c = 0, який опрацьовувати не потрібно.
Вихідні дані Для кожного запиту виведіть, скільки кордонів потрібно перетнути, щоб дістатись від c_a до c_b.