좀비 박살내기

당신은 Zombie Smash를 플레이하고 있다. 이 게임의 목표는 묘지의 무덤에서 좀비들이 튀어나올 때 믿음직한 Zombie Smasher로 좀비들을 박살내는 것이다. 묘지는 평평한 2차원 격자로 표현된다. 각 좀비는 격자의 어떤 (X, Y) 칸에 있는 무덤에서 튀어나와 1000밀리초(ms) 동안 제자리에 서 있다가 다시 무덤 속으로 사라진다. 한 번에 하나의 무덤 주변에는 최대 하나의 좀비만 서 있을 수 있다.

현재 위치에 인접한 8개의 칸 중 어느 칸으로든 100ms 만에 이동할 수 있다. 즉, 현재 위치에서 북쪽, 동쪽, 남쪽, 서쪽, NW, NE, SW, SE 방향으로 이동할 수 있다. 어떤 칸을 현재 좀비가 차지하고 있더라도 그 칸을 통과하거나 그 칸에 서 있을 수 있다. 좀비가 서 있는 칸에 도달하면 즉시 그 좀비를 박살낼 수 있지만, 좀비를 하나 박살낸 뒤에는 다른 좀비를 박살낼 수 있게 되기까지 Zombie Smasher가 재충전되는 데 750ms가 걸린다. Zombie Smasher가 재충전되는 동안에도 이동할 수 있다. 예를 들어, (0, 0)에 있는 좀비를 박살낸 직후에는 다음과 같다.

• (1, 1)에 있는 좀비에게 도달하여 박살내는 데 750ms가 걸리거나

• (20, 20)에 있는 좀비에게 도달하여 박살내는 데 2000ms가 걸린다.

게임 시작 시점(시간=0)에는 (0, 0) 칸에서 시작한다. 한 레벨을 플레이한 뒤, 최적으로 플레이했다면 몇 마리의 좀비를 박살낼 수 있었는지 알고 싶다.

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 30초. 1 ≤ T ≤ 100. -1000 ≤ $X_{i}$, $Y_{i}$ ≤ 1000. 0 ≤ $M_{i}$ ≤ 100000000 = $10^{8}$. 두 좀비가 같은 시간에 같은 위치에 있는 일은 절대 없다. 다시 말해, 한 좀비가 시간 t에 (x, y)에 나타난다면, (x, y)에 나타나는 다른 모든 좀비는 (t - 1001) 이전 또는 그 시각에 나타나거나, (t + 1001) 이후 또는 그 시각에 나타나야 한다.

테스트 세트 1 (Visible Verdict)

1 ≤ Z ≤ 8.

테스트 세트 2 (Hidden Verdict)

1 ≤ Z ≤ 100.

첫 번째 줄에는 테스트 케이스의 수인 하나의 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 해당 레벨의 좀비 수인 하나의 정수 Z가 포함된 줄로 시작한다.

다음 Z개의 줄에는 각각 공백으로 구분된 3개의 정수가 주어지며, 주어진 좀비가 나타나고 사라지는 위치와 시각을 나타낸다. i^{번째} 줄에는 정수 $X_{i}$, $Y_{i}$, $M_{i}$이 주어진다. 각 값의 의미는 다음과 같다.

• $X_{i}$는 좀비 i가 나타나는 칸의 X좌표이다.

• $Y_{i}$는 좀비 i가 나타나는 칸의 Y좌표이다.

• $M_{i}$는 게임 시작 후 좀비 i가 나타나는 시각을 밀리초 단위로 나타낸 값이다. 좀비를 박살낼 수 있는 시간 구간은 양 끝을 포함한다. 충전된 Zombie Smasher를 가지고 $[M_{i}, M_{i} + 1000]$ 범위 내의 어느 시각에든 해당 칸에 도달하면, 그 칸의 좀비를 박살낼 수 있다.

각 테스트 케이스마다 "Case #c: d"를 포함하는 한 줄을 출력한다. 여기서 c는 (1부터 시작하는) 케이스 번호이고, d는 이 레벨에서 박살낼 수 있었던 좀비 수의 최댓값이다.