Zombie Smash (Small)

Zombie Smash is a game where you smash zombies with your Zombie Smasher as they pop out of graves in a graveyard. The graveyard is a flat 2D grid. Each zombie pops out of a grave at some cell $(X, Y)$, stands in place for 1000 milliseconds, then drops back into the grave. At most one zombie stands at a grave at a time.

You move to any one of the 8 cells adjacent to your own in 100 milliseconds, so you can step north, east, south, west, northwest, northeast, southwest, or southeast. You may walk through or stand on a cell that a zombie occupies. You smash a zombie the instant you reach the cell it stands on, but after a smash the Zombie Smasher takes 750 milliseconds to recharge, and during that time you cannot smash the next zombie. You are free to keep moving while it recharges. For example, right after smashing a zombie at $(0, 0)$:

• reaching and smashing a zombie at $(1, 1)$ takes 750 milliseconds,
• reaching and smashing a zombie at $(20, 20)$ takes 2000 milliseconds.

At time $t = 0$, when the game starts, you stand at cell $(0, 0)$ with a fully charged smasher. After a level ends, work out how many zombies you could have smashed with optimal play.

The first line contains a single integer $T$, the number of test cases. Each test case starts with a line containing a single integer $Z$, the number of zombies in the level.

The next $Z$ lines each contain three space-separated integers $X_i$, $Y_i$ and $M_i$, giving the location and the time at which one zombie appears.

• $X_i$ is the $X$ coordinate of the cell where zombie $i$ appears.
• $Y_i$ is the $Y$ coordinate of the cell where zombie $i$ appears.
• $M_i$ is the time at which zombie $i$ appears, in milliseconds after the start of the game. The interval in which a zombie can be smashed is inclusive: if you reach its cell at any time in $[M_i, M_i + 1000]$ with a charged Zombie Smasher, you smash that zombie.

Limits

• $1 \le T \le 100$
• $1 \le Z \le 8$
• $-1000 \le X_i, Y_i \le 1000$
• $0 \le M_i \le 10^8$
• Two zombies are never in the same location at the same time. If one zombie appears at $(x, y)$ at time $t$, then any other zombie appearing at $(x, y)$ appears at or before $t - 1001$, or at or after $t + 1001$.

For each test case, print one line in the form Case #c: d, where $c$ is the test case number starting from 1 and $d$ is the largest number of zombies you could have smashed in that level.