Divisor Game

Bajtuś and Bituś are playing a new game. At the start, a single integer $N$ (with $N > 1$) is written on the board. The players move alternately: on each move the current player replaces the number on the board with one of its divisors that is different from the number itself. The instant a player writes the number $1$, the game ends.

For every divisor $d$ of $N$ other than $N$ itself, two fixed values $a(d)$ and $b(d)$ are given. Whenever Bajtuś writes $d$ on the board he scores $a(d)$ points, and whenever Bituś writes $d$ he scores $b(d)$ points. Each player plays to maximize his own advantage, that is, the difference between his own total score and his opponent's total score.

Bituś has already fixed $N$ and all of the scores. Bajtuś, in turn, gets to decide which of the two boys makes the first move. Assuming both play optimally, determine the advantage of the starting player in each of the two cases: when Bajtuś starts, and when Bituś starts.

The first line contains a positive integer $t$, the number of test cases. The test cases follow.

Each test case begins with a line of four integers $n_1$, $n_2$, $n_3$ and $D$ ($1 \le n_i \le 5 \cdot 10^6$, $1 < n_1 n_2 n_3 \le 8 \cdot 10^{18}$). Their product $N = n_1 \cdot n_2 \cdot n_3$ is the number initially written on the board, and $D$ is the number of positive divisors of $N$.

The next $D - 1$ lines give the scores of the divisors of $N$ other than $N$, listed in increasing order of the divisor. The $i$-th of these lines contains two integers $a(d)$ and $b(d)$ ($-10^9 \le a(d), b(d) \le 10^9$), the points awarded to Bajtuś and to Bituś respectively for writing $d$, where $d$ is the $i$-th smallest divisor of $N$.

The sum of $D$ over all test cases does not exceed $10^6$.

For each test case print one line with two integers $A$ and $B$. $A$ is the advantage of the starting player when Bajtuś moves first, and $B$ is the advantage of the starting player when Bituś moves first, both under optimal play.

In the first sample test case $N = 7$ is prime, so the starting player can only write $1$, which ends the game at once and awards that player the score attached to $1$. In the second sample test case $N = 4$: the player to move prefers to write $2$ and leave the opponent as the one forced to write $1$.