You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

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

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

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

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

Description

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

1. $k$ 是搬走的件数，不是年货的种数。$k$ 可以比 $n$ 大，例如只有 2 种年货时，也可以一次搬走 100 件。
2. 每种年货都有无限多件，所以同一种年货可以拿任意多件，不同种也可以混着拿。
3. 一种搬法只由“每种年货分别拿了几件”决定，和拿取的先后顺序无关。

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

其中 $S$ 是包含每种年货无限多件的可重集合；$S'$ 表示从箱子里取出的 $k$ 件年货。由于同一种年货有无限多件，$S'$ 中允许出现重复的价值，不能按“集合里的元素互不相同”来理解。

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

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

再算两个 $k$：$f(1)=\gcd(3,6)=3$，$f(3)=\gcd(9,12,15,18)=3$。事实上对任意 $k$ 都有 $f(k)=3$，所以最大值是 $3$，最早在 $k=1$ 时取到。这正是样例一第一组数据输出 3 1 的原因。

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

注意，这里说的“最大值不存在”并不是某个 $k$ 没有 $f(k)$，而是随着 $k$ 越来越大，$f(k)$ 可以无限增大、根本没有上界。这时就输出题面规定的 happy new year。

令 $k$ 取遍所有正整数，请你帮鼠鼠求出 $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.