변환된 혜성

슈퍼맨은 지구에서 크립톤으로 가던 도중 웜홀에 휘말려 어딘지 모를 곳으로 순식간에 이동했다. 그는 예전에 지구에서 보던 주기 혜성들을 기억하고 있고, 지금 있는 곳에서도 몇몇 주기 혜성을 볼 수 있다. 이 혜성들로 방향을 가늠하려 하지만, 먼저 어느 혜성이 어느 혜성인지 짝을 맞춰야 한다.

여기서 말하는 혜성은 주기 가우스 초혜성(periodic Gaussian hyper-comet) 이다. 주기 가우스 초혜성은 수열 $(p_1, p_2, \ldots, p_n)$ 이며, 각 $p_i = (x_i, y_i)$ 는 정수 좌표를 가지는 2차원 점이다. 혜성은 $p_i$ 를 지난 뒤 $p_{i+1}$ 을 지나고, 이 수열은 주기적이어서 $p_n$ 다음에는 다시 $p_1$ 을 지난다(첨자는 $n$ 으로 나눈 나머지로 해석한다). 또한 가우스 초혜성은 모든 $i$ 에 대해 $p_i \neq p_{i+1}$ 이고 $p_1 \neq p_n$ 을 만족한다.

슈퍼맨은 공간과 시간 양쪽으로 방향 감각을 잃었다. 공간의 측면에서, 예전에 알던 혜성은 전체 점들이 회전 되고, 두 축이 같은 양의 배율로 확대·축소 되고, 평행이동 된 모습으로 보일 수 있다. 시간의 측면에서, 예전에 첫 번째 점이라고 기억하던 점이 더 이상 첫 번째가 아닐 수 있다.

예를 들어 지구에서 본 직각삼각형 초혜성 $((0,0),(1,0),(0,1))$ 은 지금 $((40,40),(20,20),(60,20))$ 이나 $((20,20),(60,20),(40,40))$ 처럼 보일 수 있다. 공간이나 시간을 뒤집는 것은 허용되지 않는다. 즉 이 초혜성이 $((0,1),(1,0),(0,0))$ 의 모습으로 나타나는 일은 결코 없다.

지구에서 본 가우스 초혜성 하나와 슈퍼맨이 지금 보는 가우스 초혜성 하나가 주어질 때, 두 혜성이 같은 혜성일 수 있는지 판정하여라.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$) 가 주어진다.

각 테스트 케이스는 정수 $n$ ($2 \le n \le 500,000$) 으로 시작한다. 이어지는 $n$ 개의 줄에는 각각 두 정수 $x_i\ y_i$ ($i = 1 \ldots n$) 가 공백으로 구분되어 주어지며, 이는 지구에서 본 혜성의 점들이다. 그다음 다시 $n$ 개의 줄에 각각 두 정수 $x'_i\ y'_i$ 가 주어지며, 이는 슈퍼맨이 지금 있는 곳에서 본 혜성의 점들이다.

모든 좌표는 $0$ 이상 $30,000$ 이하의 정수이다. 각 혜성에 대해 모든 $i$ 에서 $p_i \neq p_{i+1}$ 이고 $p_1 \neq p_n$ 이다.

각 테스트 케이스마다, 위에서 설명한 방향 상실(회전, 균등 확대·축소, 평행이동, 그리고 시간의 순환 이동을 포함하되 반사나 시간 역행은 없음) 하에서 지구의 점 $p_1 = (x_1, y_1)$ 이 현재의 점 $q_s = (x'_s, y'_s)$ 에 대응될 수 있는 가장 작은 양의 정수 $s$ 를 출력한다. 두 혜성이 같은 혜성일 수 없다면 $0$ 을 출력한다.