나이트 다각형

두 점 $(x_1, y_1)$과 $(x_2, y_2)$는 다음 조건 중 정확히 하나가 성립하면 나이트 이동 거리만큼 떨어져 있다고 한다.

• $|x_1 - x_2| = 2$이고 $|y_1 - y_2| = 1$
• $|x_1 - x_2| = 1$이고 $|y_1 - y_2| = 2$

이 정의는 체스에서 나이트가 움직이는 방식과 거의 같다. 예를 들어 아래 그림에는 나이트 이동 거리만큼 떨어진 점의 쌍이 세 개 있다.

정수 $p$와 $q$가 주어진다. 넓이가 $p/q$이고, 인접한 꼭짓점끼리 모두 나이트 이동 거리만큼 떨어진 단순 격자 다각형을 찾아라. 그런 다각형이 없으면 없다고 밝힌다.

다각형이 단순하다는 것은 각 꼭짓점에 정확히 두 변이 닿아 있고, 두 변이 꼭짓점 외에서는 만나지 않는다는 뜻이다. 격자 다각형은 모든 꼭짓점의 좌표가 정수인 다각형이다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 원하는 넓이의 분자와 분모인 두 정수 $p$와 $q$ ($1 \le p, q \le 10^4$)가 주어진다.

각 테스트 케이스마다 해가 없으면 정수 $-1$을 한 개 출력한다.

해가 있으면 첫 줄에 다각형의 꼭짓점 수 $n$ ($3 \le n \le 10^5$)을 출력한다. 이어서 $n$개의 줄에 꼭짓점의 좌표 $x$와 $y$ ($-10^9 \le x, y \le 10^9$)를 한 줄에 하나씩 시계 방향 또는 반시계 방향 순서로 출력한다.

다각형은 단순해야 하고, 넓이는 $\frac{p}{q}$이어야 하며, 인접한 꼭짓점끼리 모두 나이트 이동 거리만큼 떨어져 있어야 한다. 해가 여러 개이면 그중 아무거나 출력한다.

첫 번째 테스트 케이스의 출력이 나타내는 다각형은 넓이가 $\frac{18}{3} = 6$이며, 아래 그림과 같다.

세 번째 테스트 케이스의 출력이 나타내는 다각형은 넓이가 $\frac{8}{1} = 8$이며, 아래 그림과 같다.

두 번째와 네 번째 테스트 케이스에는 유효한 다각형이 없음을 보일 수 있다.