만리장성 (큰 입력)

문제

북방 유목민의 침입을 막으려고 세운 만리장성의 역사를 조사하고 있다. 이 문제에서 만리장성은 동쪽 무한대에서 서쪽 마이너스 무한대까지 직선으로 뻗어 있다. 거리가 워낙 길어서 성벽은 한 번에 완성되지 않았다. 대신 축성은 대응식으로 이루어졌다. 국경의 어느 구간이 공격당해 뚫리면, 똑같은 공격을 다시 막을 수 있는 높이까지 그 구간의 성벽을 올렸다.

북쪽 국경은 유목 부족의 공격을 자주 받았다. 각 부족은 어떤 구간을 세기 $S$ 로 공격한다. 공격을 막으려면 공격받는 구간 전체에서 성벽 높이가 $S$ 이상이어야 한다. 구간 안쪽에 높이가 $S$ 보다 낮은 지점이 하나라도 있으면 공격은 그 지점을 뚫고 성공한다. 판정은 구간의 안쪽만 본다. 두 구간이 끝점 하나에서만 맞닿는다면 서로 겹치지 않은 것으로 본다.

공격이 성공해도 성벽은 부서지지 않는다. 공격이 끝나면 공격받은 구간에서 높이가 $S$ 보다 낮았던 부분이 모두 높이 $S$ 로 올라간다. 즉 그 공격을 막을 수 있는 최소한의 높이로만 올린다. 같은 날 두 번 이상 공격이 일어났다면 성벽은 그날의 공격이 모두 판정된 뒤에 올라가고, 그 공격을 전부 막을 수 있는 최소한의 높이로 올라간다.

유목 부족은 한곳에 머물지 않는다. 동쪽이나 서쪽으로 이동하면서 주기적으로 성벽을 공격한다. 이 문제에서는 각 부족이 일정한 속도로 이동하고 일정한 간격으로 공격하며, 공격 세기도 공격마다 일정한 양만큼 변한다고 가정한다. 세기는 지쳐서 줄어들 수도 있고 경험이 쌓여 늘어날 수도 있다.

기원전 250년에 성벽은 아직 없었고 모든 위치에서 높이가 0이었다. 성벽을 공격한 모든 유목 부족의 정보가 주어질 때, 성공한 공격이 몇 번인지 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 성벽을 공격한 부족의 수 $N$ 이 주어진다. 이어지는 $N$ 개 줄에는 부족 하나를 설명하는 정수 여덟 개 $d_i$ , $n_i$ , $w_i$ , $e_i$ , $s_i$ , $\Delta d_i$ , $\Delta p_i$ , $\Delta s_i$ 가 공백으로 구분되어 주어진다.

$d_i$ : 이 부족이 처음 공격한 날. 기원전 250년 1월 1일이 0일이다.
$n_i$ : 이 부족의 공격 횟수
$w_i$ , $e_i$ : 첫 공격에서 공격받은 구간의 서쪽 끝과 동쪽 끝
$s_i$ : 첫 공격의 세기
$\Delta d_i$ : 연속한 두 공격 사이의 날짜 간격
$\Delta p_i$ : 연속한 두 공격 사이에 이 부족이 동쪽으로 이동한 거리. 음수이면 서쪽으로 이동한다.
$\Delta s_i$ : 공격마다 변하는 세기의 양

제한

$1 \le T \le 20$
$1 \le N \le 1000$
$1 \le n_i \le 1000$
$0 \le d_i$
$1 \le \Delta d_i \le 676060$
$d_i + (n_i - 1) \times \Delta d_i \le 676060$
$1 \le s_i \le 10^6$
$-10^5 \le \Delta s_i \le 10^5$
$s_i + (n_i - 1) \times \Delta s_i \ge 1$
$-10^6 \le w_i < e_i \le 10^6$
$-10^5 \le \Delta p_i \le 10^5$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 성공한 공격의 수이다.

설명

첫 번째 예제의 첫 테스트 케이스에서 1번 부족은 세 번 공격한다. 0일에 구간 $[0, 2]$ 를 세기 10으로, 2일에 $[3, 5]$ 를 세기 8로, 4일에 $[6, 8]$ 을 세기 6으로 공격하고 세 번 모두 성공한다. 2번 부족은 세 번 모두 세기 8로 공격한다. 10일에 $[2, 3]$ 을 공격해 성공하고(예를 들어 위치 2.5에서 성벽 높이가 아직 0이다), 17일에 $[4, 5]$ 를 공격해 실패하며( $[3, 5]$ 의 성벽이 이미 높이 8이라 $[4, 5]$ 를 덮는다), 24일에 $[6, 7]$ 을 공격해 성공한다(그곳의 성벽은 높이 6이었다).

두 번째 테스트 케이스에서는 세 부족의 공격이 서로 엇갈린다.

0일: 2번 부족이 $[0, 1]$ 을 세기 7로 공격해 성공한다.
1일: 1번 부족이 $[0, 5]$ 를 세기 10으로, 2번 부족이 $[2, 3]$ 을 세기 9로 공격한다. 두 공격이 같은 날 일어났으므로 1번 부족의 공격 뒤에 올라간 성벽은 2번 부족을 막지 못하고, 둘 다 성공한다.
2일: 2번 부족이 $[4, 5]$ 를 세기 11로 공격해 성공한다. 그곳의 성벽은 높이 10이었다.
3일: 1번 부족이 $[8, 13]$ 을 세기 10으로 공격해 성공한다. 같은 날 3번 부족이 $[0, 5]$ 를 세기 1로 공격하지만 그곳의 성벽이 높이 10과 11이라 실패한다.
4일: 3번 부족이 $[4, 9]$ 를 세기 1로 공격해 성공한다. 5와 8 사이에는 성벽이 없었다.
5일: 3번 부족이 $[8, 13]$ 을 세기 1로 공격하지만 높이 10인 성벽이 있어 실패한다.