Description

小任是个财迷，现在他正在玩一个可以获得钱的游戏。

一开始小任的钱包是空的，现在有一个由 $n$ 个正整数组成的数组 $a$，可以进行以下操作直到数组为空， 选择其中一个数组中存在的数字 $x$,将其中一个 $x$ 从数组中移除，$sum$ 表示数组中剩余元素的和，这样一次操作之后小任将获得 $x\times sum$ 块钱。(在数组中删除元素是永久删除)。

问在无法进行的操作之后，小任最多能够获得多少钱，有多少种让小任取得最多钱的取法.

由于输出内容可能很大，最大获得金额数量和取法数量均需要对 $998244353$ 取模。

一个取法的序列可以表示为 $b_1 ,b_2,.... b_n$，其中 $b_i$ 表示为每次选择取走的数字。 两个取法被认为不同，当且仅当两个取法的序列存在一个位置 $i$ 使得 $b_i$ 不同。

Format

Input

本题有多组测试。

第一行给出一个数字 $t$，其中 $1\leq t \leq 10^4$，表示测试的数量。

每组测试一共包含两行，

第一行有一个整数 $n$，其中 $1 \leq n \leq 2\times 10^5$，表示数组的大小，

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示数组中第 $i$ 个元素的值，其中 $1\leq a_i \leq n$。

题目确保所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

Output

输出 $t$ 行，每行包含两个整数，分别表示小任最多能获得的金额，以及小任获得最多金额的取法数量。

Samples

1
3
1 1 1

3 1

Note

第一组数据，所以小任每次都只能选择数字 $1$,

第一次操作，小任选择数字 $1$，数组中剩余元素和为 $2$，小任一共获得 $2$ 块钱。

第二次操作，小任选择数字 $1$，数组中剩余元素和为 $1$, 小任一共获得 $1$ 块钱。

第三次操作，小任选择数字 $1$，数组中剩余元素和为 $0$, 小任一共获得 $0$ 块钱。

所以小任最多获得 $3$ 块钱，并且只有一种选择方法。

Limitation

2s, 256KiB for each test case.