Submit | All submissions | Best solutions | Back to list |

## 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 N_{i}, number of enemies. Next N_{i} lines each contains 3 space separated integers x, y, and r, the position and radius of the hitbox of each enemy.

- N
_{i}< 125000 - N
_{1}+ N_{2}+ ... + N_{T}< 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 1Output:3

2

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 |