규칙을 어기는 기사

검은 왕의 나라는 끝없이 펼쳐진 평면이고, 검은 칸과 흰 칸으로 빈틈없이 나뉘어 있다. 무한히 큰 체스판을 떠올리면 된다. 칸 하나의 넓이는 정확히 1제곱미터이고, 칸은 정사각 격자 위에 가지런히 놓여 있다.

점프살롯 경은 이 나라에 사는 기사다. 법에 따르면 기사는 한 칸의 중심에서 다른 칸의 중심으로 뛰어야 하고, 두 중심 사이의 거리는 정확히 $\sqrt{D}$ 미터여야 한다. 체스에서는 $D$가 5로 고정되어 있지만, 여기서는 다른 값도 다룬다. 법이 정한 $D$는 두 제곱수의 합으로 쓸 수 있다. 그렇지 않으면 기사가 한 발짝도 움직이지 못하기 때문이다.

점프살롯 경은 규칙을 지키기 싫어한다. 한 번에 $\sqrt{D}$ 미터씩 뛰는 것은 그대로 지키지만, 칸의 중심에 착지해야 한다는 조건은 무시한다. 칸의 꼭짓점에 내려앉기도 하고, 두 칸의 경계선 위에 내려앉기도 한다. 편한 대로 평면 위 아무 점에나 착지한다. 아래 두 그림은 $D = 5$일 때 가로로 두 칸, 세로로 세 칸 떨어진 곳까지 가는 경로다.

a) 규칙을 지키는 보통 기사의 경로.

b) 규칙을 어기는 점프살롯 경의 경로.

점프살롯 경은 좌표가 $(0, 0)$인 칸의 중심에서 출발해 좌표가 $(X, Y)$인 칸의 중심에 도착해야 한다. 가는 길을 막는 것은 아무것도 없다. 필요한 점프 횟수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$)

이어지는 $T$개의 줄에는 각각 세 정수 $D$, $X$, $Y$가 공백으로 구분되어 주어진다. $D$는 한 번에 뛰는 거리의 제곱이고, $(X, Y)$는 도착할 칸의 좌표다. ($1 \le D \le 10^8$, $-10^4 \le X, Y \le 10^4$) $D$는 항상 두 제곱수의 합으로 나타낼 수 있다.

각 테스트 케이스마다 목적지에 닿는 데 필요한 점프 횟수의 최솟값 $J$를 한 줄에 하나씩 출력한다.