좀비 스매시 (작은 입력)

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

당신은 지금 있는 칸에 인접한 8칸 중 어디로든 100밀리초에 이동한다. 즉 북, 동, 남, 서, 북서, 북동, 남서, 남동으로 움직인다. 좀비가 서 있는 칸도 지나가거나 그 위에 서 있을 수 있다. 좀비가 서 있는 칸에 도착하면 그 좀비를 즉시 부순다. 다만 한 마리를 부수고 나면 좀비 스매셔가 다시 충전되기까지 750밀리초가 걸리고, 그동안에는 다음 좀비를 부수지 못한다. 충전 중에도 이동은 자유롭다. 예를 들어 $(0, 0)$에서 좀비를 부순 직후라면 이렇다.

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

게임이 시작하는 시각 $t = 0$에 당신은 칸 $(0, 0)$에 있고 스매셔는 충전이 끝난 상태다. 한 판이 끝난 뒤, 최적으로 움직였다면 좀비를 최대 몇 마리 부술 수 있었는지 구하자.

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

이어지는 $Z$개 줄에는 좀비 한 마리가 나타나는 위치와 시각을 나타내는 정수 세 개 $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 8$
• $-1000 \le X_i, Y_i \le 1000$
• $0 \le M_i \le 10^8$
• 같은 칸에 두 좀비가 동시에 서 있는 일은 없다. 어떤 좀비가 시각 $t$에 $(x, y)$에 나타났다면, 같은 칸에 나타나는 다른 좀비는 $t - 1001$ 이하이거나 $t + 1001$ 이상인 시각에 나타난다.

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