포켓 볼

각 변의 길이가 1인 정사각형 당구대가 있고, 네 모서리마다 포켓이 하나씩 있습니다. 공은 한 모서리에서 출발해 직선으로 움직입니다. 모서리가 아닌 지점에서 당구대의 변에 부딪히면 거울처럼 반사되어 계속 나아가며, 마지막으로 어떤 모서리에 도달하면 그 포켓에 빠집니다.

당구대의 네 변을 각각 N(북), S(남), E(동), W(서)로, 네 모서리를 아래 그림처럼 1, 2, 3, 4로 표시합니다. 당구대를 평면 위에 놓아 모서리 1이 원점에 오고, 변 S는 x축과, 변 W는 y축과 나란하도록 합니다.

공은 원점(모서리 1)에서 출발합니다. 공이 모서리 1에서 출발하는 직선의 기울기가 주어질 때, 공이 부딪히는 변들의 순서와 마지막으로 빠지는 포켓의 모서리를 구하세요.

예를 들어 출발 기울기가 $3/5$이면 공은 모서리 1에서 출발해 변 E, N, W, E, S, W 순서로 부딪힌 뒤 모서리 3의 포켓에 빠집니다. 그 궤적은 아래 그림과 같습니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어지는 각 테스트 케이스는 한 줄에 두 정수 $p$, $q$ ($1 \le p, q \le 100$)로 주어지며, 몫 $p/q$가 공이 모서리 1에서 출발하는 직선의 기울기입니다.

각 테스트 케이스마다 두 줄을 출력합니다. 첫 줄에는 공이 부딪히는 변의 개수를 출력합니다. 둘째 줄에는 공이 부딪히는 변들의 순서와 마지막으로 빠지는 포켓의 모서리 번호를 공백 하나로 구분해 차례로 출력합니다. 공이 어떤 변에도 부딪히지 않으면 이 줄에는 모서리 번호만 출력합니다. 공이 어떤 모서리에도 도달할 수 없으면 첫 줄에 대신 $-1$을 출력합니다.