There is a beautiful garden in Marjar University. Recently, Edward, the headmaster of Marjar University, decided to build a garden water sprinkler system. The system consists of three sprinklers.

Assuming that Marjar University is an infinite plane, the garden is a circle whose center is at (`X _{0}`,

- The three sprinklers should not in the same line.
- The last sprinkler should be located inside or on the boundary of the garden.
- The coordinates of the sprinklers must be integers.
- Twice the area of the triangle that the three sprinklers form should equals
`S`.

Under these conditions, Edward wants to know the number of possible positions for the last sprinkler. Please write a program to help him!

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains an integer `S` (1 <= `S` <= 10^{8}). The next line contains three integers `X _{0}`,

It is guaranteed that the absolute value of all input coordinates will not exceed 10^{8} and the positions of the two existing sprinklers are different.

提交代码