좀비 스매시 (라지)

좀비 스매시를 하고 있다. 묘지의 무덤에서 좀비가 튀어나오면 좀비 스매셔로 내리치는 게임이다. 묘지는 평평한 2차원 격자다. 좀비는 각각 어떤 칸 $(X, Y)$에서 튀어나와 그 자리에 1000밀리초 동안 서 있다가 다시 무덤 속으로 사라진다. 한 무덤에 동시에 서 있는 좀비는 최대 한 마리다.

지금 있는 칸과 인접한 8개의 칸 중 어디로든 100밀리초 만에 이동한다. 즉 북, 동, 남, 서, 북서, 북동, 남서, 남동으로 갈 수 있다. 좀비가 서 있는 칸도 지나가거나 그 위에 서 있을 수 있다. 좀비가 서 있는 칸에 도착하면 그 좀비를 즉시 내리친다. 한 번 내리치고 나면 좀비 스매셔를 다시 쓸 때까지 750밀리초의 충전 시간이 필요하다. 충전되는 동안에도 이동할 수 있다. 예를 들어 $(0, 0)$의 좀비를 내리친 직후라면 이렇게 된다.

• $(1, 1)$의 좀비에게 도착해 내리치기까지 750밀리초가 걸린다.
• $(20, 20)$의 좀비에게 도착해 내리치기까지 2000밀리초가 걸린다.

시각 0에 칸 $(0, 0)$에서 시작한다. 한 판을 끝낸 뒤, 최적으로 플레이했다면 좀비를 최대 몇 마리 내리칠 수 있었는지 알고 싶다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 그 판에 나오는 좀비의 수 $Z$가 주어진다.

이어지는 $Z$개 줄에는 좀비 $i$가 언제 어디에 나타나는지를 나타내는 정수 세 개 $X_i$, $Y_i$, $M_i$가 공백으로 구분되어 주어진다.

• $X_i$는 좀비 $i$가 나타나는 칸의 x좌표다.
• $Y_i$는 좀비 $i$가 나타나는 칸의 y좌표다.
• $M_i$는 좀비 $i$가 나타나는 시각이고, 게임 시작 후 밀리초로 잰다. 내리칠 수 있는 구간은 양 끝을 포함한다. 충전이 끝난 좀비 스매셔를 들고 $[M_i, M_i + 1000]$ 안의 어느 시각에든 그 칸에 도착하면 그 칸의 좀비를 내리친다.

제한

• $1 \le T \le 100$
• $1 \le Z \le 100$
• $-1000 \le X_i, Y_i \le 1000$
• $0 \le M_i \le 100000000$
• 같은 시각에 같은 자리에 있는 좀비는 없다. 어떤 좀비가 시각 $t$에 $(x, y)$에 나타나면, $(x, y)$에 나타나는 다른 좀비는 모두 $t - 1001$ 이전이거나 $t + 1001$ 이후에 나타난다.

각 테스트 케이스마다 "Case #c: d" 형식으로 한 줄씩 출력한다. c는 1부터 시작하는 테스트 케이스 번호이고, d는 그 판에서 내리칠 수 있는 좀비 수의 최댓값이다.