Alex is a professional computer game player.
These days, Alex is playing an interstellar game. This game is played in an infinite 2D universe, and Alex's spaceship starts at $(0, 0)$ in the beginning. Because the distances between different galaxies are too long (conventional thrusters cannot reach the destination in an acceptable amount of time), movement can only be done by "jump". If his spaceship has jump skill $(a, b)$ and he is located at $(x, y)$, he can reach $(x + a, y + b)$ or $(x -a, y -b)$ immediately. He can use jump skills continuously at any time, and the jump skills will not disappear.
In the game, the following $Q$ events, which have two types, will happen in order.
Alex wonders how many rewards he can get if he plays optimally.
The first line of the input gives the number of test cases, $T " "(1 <= T <= 10^4)$. $T$ test cases follow.
For each test case, the first line contains a integer $Q " "(1 <= Q <= 10^5)$, where $Q$ is the number of the following events.
Each of the following $Q$ lines contains three or four integers $t_i " "(1 <= t_i <= 2)$, $x_i, y_i " "(0 <= x_i, y_i <= 10^6)$ and maybe $w_i " "(1 <= w_i <= 10^9)$, describing the following events.
The sum of $Q$ in all test cases doesn't exceed $10^6$.
For each test case, output one line containing "_Case #x: y_", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the maximum rewards Alex can get.
## Input
The first line of the input gives the number of test cases, $T " "(1 <= T <= 10^4)$. $T$ test cases follow.For each test case, the first line contains a integer $Q " "(1 <= Q <= 10^5)$, where $Q$ is the number of the following events.Each of the following $Q$ lines contains three or four integers $t_i " "(1 <= t_i <= 2)$, $x_i, y_i " "(0 <= x_i, y_i <= 10^6)$ and maybe $w_i " "(1 <= w_i <= 10^9)$, describing the following events.The sum of $Q$ in all test cases doesn't exceed $10^6$.
## Output
For each test case, output one line containing "_Case #x: y_", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the maximum rewards Alex can get.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ Q \in \mathbb{Z} $ be the number of events.
Let $ E = \{ (t_i, x_i, y_i, w_i) \mid i \in \{1, \dots, Q\} \} $ be the sequence of events, where:
- $ t_i \in \{1, 2\} $: event type.
- If $ t_i = 1 $: a reward at position $ (x_i, y_i) $ with value $ w_i $ is revealed.
- If $ t_i = 2 $: query for the maximum reward reachable from $ (0, 0) $ using jump skills collected so far.
Let $ J \subseteq \mathbb{Z}^2 $ be the set of jump skills acquired from type-1 events.
**Constraints**
1. $ 1 \le T \le 10^4 $
2. $ 1 \le Q \le 10^5 $ per test case
3. $ 0 \le x_i, y_i \le 10^6 $
4. $ 1 \le w_i \le 10^9 $
5. $ \sum Q \le 10^6 $ across all test cases
**Objective**
For each test case, process events sequentially.
- On type-1 event: add $ (x_i, y_i) $ to $ J $.
- On type-2 event: compute the maximum $ w_j $ among all rewards $ (x_j, y_j) $ (from previous type-1 events) such that $ (x_j, y_j) $ is reachable from $ (0, 0) $ using integer linear combinations of vectors in $ J $.
That is, for a reward at $ (x, y) $, it is reachable iff there exist integers $ c_k \in \mathbb{Z} $ such that:
$$
(x, y) = \sum_{(a_k, b_k) \in J} c_k \cdot (a_k, b_k)
$$
This is equivalent to $ \gcd(\{ a_k, b_k \mid (a_k, b_k) \in J \}) $ dividing $ \gcd(x, y) $.
**Output**
For each type-2 event, output the maximum $ w_i $ among all reachable rewards up to that point.