Migrated from Lutece 3249 六边形匹配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 双射，LGV

小 $Z$ 有一个异同寻常的坐标系， 其中 $x$ 轴正半轴与 $y$ 轴正半轴夹角为 $60$ 度。

现在，小 $Z$ 将所有横纵坐标不全为偶数，且满足 $-2 a + 1 \le x \le 2 a - 1，-2 b + 1 \le y \le 2 b - 1，-2 c + 1 \le x + y \le 2 c - 1$ 的的整点都染上了黑色。小 $Z$ 发现，染完色后的点看上去如同一个个六边形相互交接。

现在小 $Z$ 想知道想将其中一些黑点重新染为红色，但红色的点之间不能相邻的方案数。

相邻的定义：对于点 $(x,y)$，它和 $(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y + 1)$ 六个点相邻。

这个问题显然是求一个最大独立集问题，小 $Z$ 一下子就秒了，但他想知道，如果要求最大独立集的话，答案会是多少，同时如果是满足最大独立集的话，那方案数又有多少呢？

一想到最大独立集，小 $Z$ 就晕了，但小 $D$ 一下子就秒了这个问题，小 $Z$ 很怀疑小 $D$ 答案的准确性，因此他想让你给他答案从而知道小 $D$ 是否真的算对了？

Input

第一行输入一个整数 $T$ ($1 \le T \le 10$)。

接下来 $T$ 行， 分别输入 $a,b,c$ , $a,b,c$ 的含义如题意所示。($1 \le a,b,c \le 10^6$ ).

Output

输出 $T$ 行 ，每行两个整数表示最大独立集的大小和满足最大独立集的方案数，方案数对 $998244353$ 取模。

PS: 最大独立集的大小无须取模，并请注意数据规模。

Samples

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

Note

如下图所示，点 $J$ 的坐标为 $(2, 1)$，点 $F$ 的坐标为 $(−1,0)$，点 $H$ 的坐标为 $(2, 0)$。在这三个点中，只有点 $H$ 是横纵坐标全为偶数的点。图中与点 $A$ 距离为 $1$ 的点有 $B,C,D,E,F,G$ 六个点。

在样例的第一组数据中，满足条件的整点有 $N,G,B,I,J,P,F,C,K,M,L,E,D,S,T$。

最多能染 $7$ 个点，方案共 $4$ 种，具体为：$\{P,N,L,B,D,J,T\}$, $\{R,M,F,B,D,J,T\}$，$\{R,M,G,E,C,J,T\}$，$\{R,M,G,E,I,S,K\}$。

在样例的第二组数据中，满足条件的整点有 $G,B,I,F,C,L,E,D$。

最多能染 $4$ 个点，方案共 $1$ 种，具体为：$\{L,G,I,D\}$。

Resources

2024 UESTC ICPC Training for Math