该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

当一个题目的答案可能很大，但又不希望考察大整数乘法的具体实现时，通常会要求输出答案对某个质数取模的

结果。现在给定一个长度为 $n$ 的正整数序列，青藤想要在删除一个元素之后，使得剩下所有元素的乘积对质数

$998244353$ 取模的结果尽可能大。他不知道应该删除哪一个元素，你能帮他找出删除一个元素后能得到的最

大取模结果吗？

注意:必须删除一个元素

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试数据的组数。

接下来描述每组测试数据：

• 第一行一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数组的长度。
• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组的元素。

所有测试数据中 $n$ 的总和不超过 $4 \times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示删除一个元素后，剩余元素的乘积对 $998244353$ 取模的最大值。

2
6
1 1 4 5 1 4
3
998244353 998244357 998244359

80
24

样例解释

第一组数据

• 删除任意一个 1 后，剩余元素的乘积为 1×4×5×1×4 = 80，模 998244353 得 80
• 删除 4 后，剩余乘积为 1×1×5×1×4 = 20，模 998244353 得 20
• 删除 5 后，剩余乘积为 1×1×4×1×4 = 16，模 998244353 得 16
• 最大值为 80

第二组数据

• 998244353 模 998244353 得 0
• 998244357 模 998244353 得 4
• 998244359 模 998244353 得 6
• 删除第一个元素（0）后，剩余元素乘积为 4×6 = 24，模 998244353 得 24
• 删除第二个元素（4）后，剩余元素乘积为 0×6 = 0，模 998244353 得 0
• 删除第三个元素（6）后，剩余元素乘积为 0×4 = 0，模 998244353 得 0
• 最大值为 24