Garden and Sprinklers

Time Limit: 2 Seconds

Memory Limit: 65536 KB


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 (X0, Y0) with radius R. Now, Edward has already determined the position for two sprinklers at (X1, Y1) and (X2, Y2). He needs to choose the position for the last sprinkler. Here are some conditions to be satisfied:

  1. The three sprinklers should not in the same line.
  2. The last sprinkler should be located inside or on the boundary of the garden.
  3. The coordinates of the sprinklers must be integers.
  4. 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 <= 108). The next line contains three integers X0, Y0 and R (1 <= R <= 108). The last line contains four integers X1, Y1, X2 and Y2.

It is guaranteed that the absolute value of all input coordinates will not exceed 108 and the positions of the two existing sprinklers are different.


For each test case, output the number of possible positions.

Sample Input

0 0 4
-1 0 1 0

Sample Output



In the sample test case, the possible positions for the last sprinkler are: (-3, 2), (-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (3, 2), (-3, -2), (-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (3, -2).