Keliang is a girl who loves computational geometry. She has drawn a special planar coordinate system where the angle between the positive $x$-axis and the positive $y$-axis is $60^\circ$.
From this system, she selects all integer points $(x, y)$ such that not both $x$ and $y$ are even, and which satisfy: $-2a + 1 \le x \le 2a - 1$ $-2b + 1 \le y \le 2b - 1$ $-2c + 1 \le x + y \le 2c - 1$
Keliang wants to color some of these points such that no two adjacent points are colored. Specifically, a point $(x, y)$ is adjacent to the six points $(x, y+1), (x, y-1), (x+1, y), (x-1, y), (x+1, y-1),$ and $(x-1, y+1)$.
Keliang wants to know the maximum number of points that can be colored under these rules, and the number of ways to achieve this maximum. Since the latter can be very large, you only need to output the number of ways modulo $998\,244\,353$. Note that the maximum number of points should not be taken modulo.
Input
The first line contains an integer $T$, representing the number of test cases. Each of the next $T$ lines contains three integers $a, b, c$, representing one test case.
Output
For each test case, output two integers on a single line: the maximum number of points that can be colored (not modulo) and the number of ways to do so modulo $998\,244\,353$.
Constraints
For all test cases: $1 \le T \le 10$, $1 \le a, b, c \le 10^6$.
| Test Case ID | $a \le$ | $b, c \le$ | Special Constraint |
|---|---|---|---|
| 1 | 3 | 3 | $a = b = c$ |
| 2 | 4 | 4 | $a = b = c$ |
| 3 | 4 | 4 | None |
| 4 | 3 | 100 | None |
| 5, 6 | 3 | 1000 | None |
| 7, 8 | 3 | 5000 | None |
| 9, 10 | 100 | 100 | $a = b = c$ |
| 11 ~ 14 | 100 | 100 | None |
| 15 | $10^5$ | $10^5$ | $a = b = c$ |
| 16 | $10^5$ | $10^5$ | None |
| 17, 18 | $10^6$ | $10^6$ | $a \cdot b \cdot c \le 10^6$ |
| 19 | $10^6$ | $10^6$ | $a = b = c$ |
| 20 | $10^6$ | $10^6$ | None |
Examples
Input 1
2 2 2 2 2 2 1
Output 1
7 4 4 1
Note
As shown in the figure below, point $J$ has coordinates $(2, 1)$, point $F$ has coordinates $(-1, 0)$, and point $H$ has coordinates $(2, 0)$. Among these three points, only point $H$ has both coordinates as even numbers. In the figure, the six points $B, C, D, E, F, G$ are at a distance of $1$ from point $A$.
In the first example test case ($a=2, b=2, c=2$), the integer points satisfying the conditions are $R, N, G, B, I, J, P, F, C, K, M, L, E, D, S, T$. The maximum number of points that can be colored is $7$, and there are $4$ ways: $\{P, N, L, B, D, J, T\}$, $\{R, M, F, B, D, J, T\}$, $\{R, M, G, E, C, J, T\}$, and $\{R, M, G, E, I, S, K\}$.
In the second example test case ($a=2, b=2, c=1$), the integer points satisfying the conditions are $G, B, I, F, C, L, E, D$. The maximum number of points that can be colored is $4$, and there is $1$ way: $\{L, G, I, D\}$.