cho.sh

벌집우주와 쿼리

시간 제한1초메모리 제한1024 MB

문제

pjshwa는 로켓을 타고 광활한 벌집우주를 여행하고 있다. 벌집우주는 아래 그림과 같은 좌표계를 사용한다.

$(x, y)$에 위치한 로켓은 방향각 $r^\circ$와, 이동할 거리 $t$를 정하여 다음 6가지 좌표 중 하나로 갈 수 있다.

방향각 $r^\circ$이동 후 좌표
$0^\circ$$(x + t, y)$
$60^\circ$$(x + t, y + t)$
$120^\circ$$(x, y + t)$
$180^\circ$$(x - t, y)$
$240^\circ$$(x - t, y - t)$
$300^\circ$$(x, y - t)$

멀미가 심한 pjshwa는 로켓의 방향을 가능한 적게 바꾸고 싶다. 가고 싶은 좌표 $Q$개가 주어질 때, $(0, 0)$에서 $0^\circ$ 방향으로 놓여 있는 로켓이 그 좌표에 도달하기 위해 필요한 최소 방향 전환 횟수를 계산하자!

입력

첫 번째 줄에 pjshwa가 가고 싶어 하는 좌표의 개수 $Q$가 주어진다. $(1 \leq Q \leq 100\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 좌표를 나타내는 정수 $x, y$가 공백으로 구분되어 주어진다. $(-10^9 \leq x, y \leq 10^9)$

출력

각 좌표마다 $(0, 0)$에서 $0^\circ$ 방향으로 놓여 있는 로켓이 해당 좌표에 도달하기 위해 필요한 최소 방향 전환 횟수를 한 줄에 하나씩 출력한다.