Beetle Dinner

Time limit2sMemory limit1024 MB

Summary

Count the integer-coordinate points on the full line through Timon and Pumbaa that lie inside or on a given circle.

Level: Medium6 of 10
Topics: Math, Number theory, Geometry
Solved: No attempts yet

Statement

Timon found many tasty beetles under a fallen tree and loudly calls Pumbaa, who is out walking, to dinner.

Near Timon and Pumbaa there is a man-made grove. The trees in this grove grow only at points with integer coordinates that lie inside or on the boundary of some circle.

To get to Timon and have dinner, Pumbaa must move along the straight line that connects the points where he and Timon are. He wants to know how many trees from this grove lie on the same line as him, Timon, and the hearty dinner.

Input

The first line contains three integers $x$ , $y$ , $r$ ( $1 \le r \le 10^9$ ): the coordinates of the center and the radius of the grove's circle. The second line contains four integers $x_t$ , $y_t$ , $x_p$ , and $y_p$ : the coordinates of Timon and Pumbaa. It is guaranteed that neither Pumbaa nor Timon is strictly inside the grove. All coordinates have absolute value at most $10^9$ .

Output

Print one number: the number of trees on Pumbaa's path to Timon.

Hint

Pumbaa cares about more than the trees on the segment between him and Timon. Points outside that segment that still lie on the same line also count.

Examples1

Example 1
Input
```
0 0 5
-10 1 10 1
```
Expected output
```
9
```