Background

新年将至，《三角洲行动》开启了年度「年货节」活动。鼠鼠们刚在零号大坝落地，就发现策划把一整个无限补给箱塞进了安全屋：里面的年货取之不尽、用之不竭。

消息一出，老六、跑刀仔和六套大佬同时往安全屋冲。策划为了防止哈夫币经济当场崩盘，连夜贴出一张告示：

“为了保证每位干员都能共同富裕，本次年货节采用「保底公约数」制度。搬多少拿多少，但拿走的总价值必须对得起数学！”

于是，一场关于 gcd 的年货大劫案开始了……

Description

无限补给箱中共有 $n$ 种年货，第 $i$ 种年货每件价值 $a_i$ 哈夫币，且每种年货都有无限多件。鼠鼠准备恰好搬走 $k$ 件年货，同一种年货可以拿任意多件。对于每一种搬法，计算这 $k$ 件年货的总价值。

定义 $f(k)$ 为所有搬法所得总价值的最大公约数，也就是策划承诺的“保底公约数”：

$$f(k) = \gcd_{S' \subseteq S,\ |S'| = k} \left( \sum_{x \in S'} x \right)$$

其中 $S$ 是包含每种年货无限件的无限向量集。

例如，年货价值为 $a = [3, 6]$ 时，搬走 $2$ 件的方案只有 $3+3$、$3+6$、$6+6$，所以

$$f(2) = \gcd(3 + 3,\ 3 + 6,\ 6 + 6) = 3$$

再比如 $a = [2, 2]$，无论搬走多少件，总价值都是 $2k$，$f(k) = 2k$ 会一路涨到天上去，最大值根本不存在。此时策划会当场破防，并高喊 happy new year。

请你帮鼠鼠求出 $f(k)$ 的最大值，以及取到最大值时最小的 $k$。特别地，如果最大值不存在，请输出 happy new year（不包含引号）。

Format

Input

该题包含多组测试数据。输入第一行包含一个整数 $T$ ($1 \le T \le 4 \times 10^5$)，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示年货的种数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$)，表示每种年货的价值。

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

Output

对于每组数据，如果 $f(k)$ 存在最大值，则输出一行两个整数，分别表示 $f(k)$ 的最大值以及取得最大值时最小的 $k$。

否则输出 happy new year（不包含引号）。

Samples

2
2
3 6
2
2 2

3 1
happy new year

2
3
1 4 7
4
4 16 28 34

3 3
6 3

Limitation

1s, 1024KiB for each test case.