Black Jack

La tierra del Rey Black es una superficie plana que se extiende infinitamente en cuadrados blancos y negros, muy similar a un tablero de ajedrez infinito. El área de cada cuadrado es exactamente 1m^2. Sir Humpsalot es un caballero que vive en la tierra del Rey Black. Por ley, los caballeros sólo podrán moverse saltando desde el centro de una plaza al centro de otro cuadrado, siempre que la distancia entre los centros es exactamente √D metros.

Aunque Sir Humpsalot realiza saltos de √D metros, no se molesta en caer en el centro de una plaza. En otras palabras, a veces cae en una esquina de un cuadrado o incluso en la frontera entre las casillas adyacentes, lo que sea más conveniente. Llegar a su destino suele ser más fácil de esta manera.

 eniendo en cuenta que Sir Humpsalot comienza en el centro de la plaza de coordenadas (0, 0) y tiene que viajar hasta el centro de la plaza de coordenadas (X, Y), su tarea consiste en calcular el número mínimo de saltos que Sir Jumpsalot necesita para llegar a su destino.

Input: La entrada empieza con una linea conteniendo un entero T, el número de casos de prueba. Luego para cada caso se encuentra una linea con 3 enteros X, Y y Z separados por espacios, indicando el cuadrado de la distancia realizada en un salto simple, y las coordenadas del destino final. 1 ≤ D ≤ 108 y −104 ≤ X, Y ≤ 104.

Output: Para cada caso de prueba, imprime una linea con un simple entero J, el minimo número de saltos necesarios para alcanzar el destino.

Input

	Output
5 5 0 0 5 2 3 25 -3 -4 100 0 -100 1 2345 6789	0 2 1 10 7183