BLMIRANA - Mayonnaise Arrow

Mirana is an archer with superpower. Every arrow she shoots will get stronger the further it travels. Mirana is currently on a warzone.

Coincidentally, there's a guy selling mayonnaise. With the power of mayonnaise, Mirana's arrow can pierce every obstacle in its way. Unfortunately, there's only enough mayonnaise to power an arrow.

Mirana stands on the (0,0) point in cartesian scale. From that point she must shoot as many enemies as possible with an arrow. Each enemy has a circle shaped hitbox. An enemy dies if the arrow travels through its hitbox. Determine the maximum number of enemies that can be shot with an arrow!

Input

First line contains T, number of wars. On the i-th war, first line contains Ni, number of enemies. Next Ni lines each contains 3 space separated integers x, y, and r, the position and radius of the hitbox of each enemy.

  • Ni < 125000
  • N1 + N2 + ... + NT < 500000
  • 1 < r < x < 1000
  • -1000 < y < 1000 

Output

For each war, output a line containing the maximum number of enemies that can be shot with an arrow.

Example

Input:
2
3
1 1 1
2 2 1
4 5 2
3
5 -4 1
10 -5 1
20 -10 1 Output: 3

Added by:Andy
Date:2016-09-04
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYPY PYTHON3
Resource:BLPCS4

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.