Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4000
It's High Noon

Time Limit: 2 Seconds      Memory Limit: 65536 KB


Mccree's ultimate skill has cooled down! He can aim at arbitrary direction and shoot all the enemies in front of him in a range of 180 degrees (A half plane, the border of which passes through Mccree. The enemies on the border will also be shot).

He can only aim for several seconds, so the range he can move in is a circle (He can aim on the border of the circle). The center of the circle is (0, 0) and the radius is \(R\). He wants to know how many enemies at most he can beat down in one shot.


There are multiple test cases. The first line of input is a integer \(T\) (\(1 \le T \le 10\)), indicating the number of test cases. For each test case:

The first line contains two integers \(N\) (\(1 \le N \le 10^5\)) and \(R\) (\(1 \le R \le 300\)), indicating the number of enemies and the radius of the circle.

The following \(N\) lines each contains two integers \(X_i\) and \(Y_i\) (\(-10^3 \le X_i, Y_i \le 10^3\)), indicating the coordinate of each enemy.


For each case output one line containing one integer, indicating the maximum number of enemies Mccree can shoot.

Sample Input

4 1
2 2
2 -2
-2 -2
-2 2

Sample Output



A solution for the sample test case is shown as follows.

Author: CHEN, Shihan
Source: ZOJ Monthly, January 2018
Submit    Status