ADAM1 - Adrita and Marbles

no tags 

Adrita loves to play with marbles at home. She has a circular table on her living room. Let it be stuck on the ground and the ground be a 2D space having only 2 coordinates x and y. She knows the equation of the circle to be x^2 + y^2 - px - qy + z = 0

She has N number of marbles of radius 1 unit. The table is not polished and Adrita has some coordinates where she wants to put the marbles.

Help her calculating the number of marbles she will place on the table. Consider the thickness of the table is negligible and if the center is on the border of the table the marble is considered to be on the table.

Input

The first line contains an integer T (1 <= T <= 10) denoting number of test cases and then T set of input follows of which. the first line contains values of p, q, z (1 <= p, q, z <= 10^6) of the equation x^2 + y^2 - px - qy + z = 0 and the next line contains an integer N (1 <= N <= 10^6) denoting the number of marbles Adrita has and then another N lines follows containing x, y ( -10^5 <= x, y <= 10^5) denoting the coordinates of the marbles.

Output

Print the number of marbles on the table.

Example

Input:
1
100 250 8125
5
30 10
-100 100
20 5
100 100
-30 10

Output:
1

hide comments
lumaks_69: 2022-01-13 20:20:37

READING:0.5h
SOLVING:1min

nadstratosfer: 2018-11-24 23:38:34

Read the statement 3 times over the last year and always assumed it was a different problem. No idea why the table's thickness or the fact that it's polished is brought up, but the most important thing is that the marble radius is negligible as the coordinates are integer. So go with simple geometry without any DP/optimization algo.

susheelgupta: 2017-12-31 08:47:47

long int cost me 3 wrong ans ;

mehul_sri: 2017-12-30 15:52:05

In the input, the 'c' is 'z' of the equation.


Added by:Sarwar
Date:2017-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All