Problem Description

Jiutiao Kelian is a girl who likes computational geometry. She drew a special plane coordinate system, where the angle between the positive $x$-axis and the positive $y$-axis is $60$ degrees.

From it, she takes all integer points whose $x$- and $y$-coordinates are not both even, and that satisfy $-2 a + 1 \le x \le 2 a - 1$, $-2 b + 1 \le y \le 2 b - 1$, and $-2 c + 1 \le x + y \le 2 c - 1$.

Kelian wants to color some of these points, but adjacent points cannot be colored at the same time. Specifically, for a point $(x, y)$, it 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)$. You may understand this together with the sample explanation.

Kelian wants to know the maximum number of points that can be colored under this rule, and the number of coloring schemes that achieve this maximum. Since the latter may be very large, for the number of schemes you only need to output it modulo $998244353$. Note that you do not need to take the maximum number of colored points modulo anything.

Input Format

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain three integers $a$, $b$, and $c$, representing one test case.

Output Format

Output $T$ lines in total. Each line contains two integers: the maximum number of points that can be colored (not taken modulo) and the number of schemes modulo $998244353$.

6
2 1 2
1 1 137
3 94 95
3 1998 1996
998244 353999 999999
50 120 150

7 4
4 1
1124 31585548
23951 33873190
1289433675488 748596399
23600 480090154

Hint

[Sample Explanation]

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 even. In the figure, the points at distance $1$ from point $A$ are the six points $\texttt{B C D E F G}$.

In the first sample test case, the integer points satisfying the conditions are $\texttt{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$ schemes, namely: $\texttt{P N L B D J T}$, $\texttt{R M F B D J T}$, $\texttt{R M G E C J T}$, and $\texttt{R M G E I S K}$.

In the second sample test case, the integer points satisfying the conditions are $\texttt{G B I F C L E D}$.

The maximum number of points that can be colored is $4$, and there is $1$ scheme, namely: $\texttt{L G I D}$.

[Constraints]

For all test points: $1 \le T \le 10$, $1 \le a, b, c \le {10}^6$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5