FHNW_final_contest_190703

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₁ + N₂ + ... + 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 1

Output:
3
2