The Great Wall (Large)

You are studying the history of the Great Wall of China, built to hold off military incursions from the north. In this problem the Great Wall runs along a straight line, from infinity in the east to minus infinity in the west. That is a lot of distance to cover, so the Wall was not built all at once. The builders worked reactively instead: whenever a stretch of the border was attacked successfully, the Wall on that stretch was raised to the height that would have stopped an identical attack.

The northern border was attacked often by nomadic tribes. Each tribe attacks some interval with a strength $S$. To repel the attack, the Wall must be at least $S$ high everywhere on the defended interval. If a single point inside the interval is lower than $S$, the attack breaches the Wall there and succeeds. Only the interior of the interval counts. Two intervals that meet at one endpoint do not overlap.

A successful attack does no damage to the Wall. After the attack, every attacked part of the Wall that was lower than $S$ is raised to height $S$, so the Wall grows in the minimal way that would have stopped the attack. If two or more attacks happen on the same day, the Wall is raised only after all of them resolve, and it is raised in the minimal way that would stop all of them.

Nomadic tribes do not stay in one place. They move east or west and attack the Wall periodically. In this problem each tribe moves at a constant speed and attacks at constant intervals, and the strength of its attacks changes by a constant amount after each attack. The strength can shrink from attrition or grow from experience.

In 250 BC the Wall did not exist yet and its height was zero everywhere. Given the full description of every nomadic tribe that attacked the Wall, determine how many attacks succeeded.

The first line contains the number of test cases $T$. Each test case begins with a line containing the number of tribes $N$ that attacked the Wall. $N$ lines follow. The $i$th of them describes one tribe with eight space separated integers $d_i$, $n_i$, $w_i$, $e_i$, $s_i$, $\Delta d_i$, $\Delta p_i$, $\Delta s_i$.

• $d_i$: the day of the tribe's first attack, where 1 January 250 BC is day 0
• $n_i$: the number of attacks from this tribe
• $w_i$, $e_i$: the westmost and eastmost points of the Wall attacked on the first attack
• $s_i$: the strength of the first attack
• $\Delta d_i$: the number of days between two consecutive attacks by this tribe
• $\Delta p_i$: the distance the tribe travels east between two consecutive attacks. A negative value means it travels west.
• $\Delta s_i$: the change in strength between two consecutive attacks

Limits

• $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$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of attacks that succeed.

In the first test case of the first example, tribe 1 attacks three times: on day 0 it hits the interval $[0, 2]$ with strength 10, on day 2 it hits $[3, 5]$ with strength 8, and on day 4 it hits $[6, 8]$ with strength 6. All three succeed. Tribe 2 attacks three times with strength 8 each time. On day 10 it hits $[2, 3]$ and succeeds (at position 2.5, for example, the Wall is still zero). On day 17 it hits $[4, 5]$ and fails, because the Wall on $[3, 5]$ is already 8 high and covers $[4, 5]$. On day 24 it hits $[6, 7]$ and succeeds, because the Wall there was 6 high.

In the second test case the attacks of three tribes interleave.

• Day 0: tribe 2 attacks $[0, 1]$ with strength 7 and succeeds.
• Day 1: tribe 1 attacks $[0, 5]$ with strength 10 and tribe 2 attacks $[2, 3]$ with strength 9. Both succeed, because the attacks are simultaneous and the Wall built after the first tribe's attack is not there in time to stop the second tribe.
• Day 2: tribe 2 attacks $[4, 5]$ with strength 11 and succeeds. The Wall there was 10 high.
• Day 3: tribe 1 attacks $[8, 13]$ with strength 10 and succeeds. On the same day tribe 3 attacks $[0, 5]$ with strength 1 and fails, because the Wall there is 10 and 11 high.
• Day 4: tribe 3 attacks $[4, 9]$ with strength 1 and succeeds. There was no Wall between 5 and 8.
• Day 5: tribe 3 attacks $[8, 13]$ with strength 1 and fails, because a Wall of height 10 is there.