Grammy 拥有一个特殊的二维坐标系：$X$ 轴正半轴与 $Y$ 轴正半轴之间的夹角为 $60$ 度。

考虑以下图。顶点为所有满足以下条件的整点坐标 $(x, y)$：$x, y$ 中至少有一个是奇数，且 $-2a + 1 \le x \le 2a - 1$，$-2b + 1 \le y \le 2b - 1$，$-2c + 1 \le x + y \le 2c - 1$。从 $(x, y)$ 出发的边连接到 $(x, y + 1)$，$(x, y - 1)$，$(x + 1, y)$，$(x - 1, y)$，$(x + 1, y - 1)$ 和 $(x - 1, y + 1)$。

求该图中最大独立集的大小。此外，求出满足条件的集合数量，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含三个整数 $a, b, c$ ($1 \le a, b, c \le 10^6$)。

输出格式

输出 $T$ 行。每行包含两个整数：最大独立集的大小和满足条件的集合数量。请注意，大小不应对 $998\,244\,353$ 取模。

样例

样例输入 1

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

样例输出 1

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

说明

下图展示了样例中第一个和第二个测试用例的情况。

测试用例 1 和 2 的图片。

点 $J$ 的坐标为 $(2, 1)$，点 $F$ 的坐标为 $(-1, 0)$，点 $H$ 的坐标为 $(2, 0)$。在这三个点中，只有 $H$ 的 $X$ 坐标和 $Y$ 坐标均为偶数。点 $A$ 的邻居是 $BCDEFG$。

在第一个测试用例中，满足条件的点为 $NGBIJPFCKMLEDST$。 最大独立集的大小为 $7$，共有 $4$ 种方案：$PNLBDJT, RMFBDJT, RMGECJT, RMGEISK$。

在第二个测试用例中，满足条件的点为 $GBIFCLED$。 最大独立集的大小为 $4$，共有 $1$ 种方案：$LGID$。