Zombie Smash (Large)

You are playing Zombie Smash. Zombies pop out of graves in a graveyard, and you smash them with your Zombie Smasher. The graveyard is a flat 2D grid. Each zombie pops out of a grave at some cell $(X, Y)$, stands there for 1000 milliseconds, then drops back into the grave. At most one zombie stands at a grave at any moment.

You move to any one of the 8 cells adjacent to your cell in 100 ms, so you can go north, east, south, west, northwest, northeast, southwest and southeast. You may walk through a cell or stand on it even while a zombie occupies it. Reaching the cell of a standing zombie smashes that zombie instantly, but after a smash the Zombie Smasher takes 750 ms to recharge before it can smash again. You may 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 ms, or
• reaching and smashing a zombie at $(20, 20)$ takes 2000 ms.

You start on cell $(0, 0)$ at time 0. After you play a level, you want to know how many zombies you could have smashed with optimal play.

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

The next $Z$ lines each contain 3 space separated integers $X_i$, $Y_i$ and $M_i$, describing where and when zombie $i$ 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 the zombie can be smashed includes both endpoints: if you reach the cell at any time in $[M_i, M_i + 1000]$ with a charged Zombie Smasher, you smash the zombie in that cell.

Limits

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

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