Description

某天，unbengable 同学参加了一个有奖问答，只要答对问题就可以获得奖品。由于成天摆烂，无所事事，水平低下的 unbengable 同学一筹莫展，于是他求助了你帮他完成这个问答。

给一个长度为 $n$ 的正整数数组 $a_1,a_2,\ldots,a_n$，选定任意三个数 $i,j,k$，有以下条件：

1. $i,j,k$ 三个数互不相同；
2. $1\leq i,j,k\leq n$，其构成的三元组有序即 $(i,j,k)\neq(i,k,j)$；
3. 三个数 $a_i\leq a_j \leq a_k$，构成等比数列，且公比为任意正整数；
4. 三个数 $a_i\leq a_j \leq a_k$，构成等比数列，且公比为 $d=24$。

你需要求出：

• 满足条件 $1,2,3$ 的三元组 $(i,j,k)$ 个数 $ans$；
• 满足条件 $1,2,4$ 的三元组 $(i,j,k)$ 个数 $ans_d$。

unbengable 同学请你帮他计算 $ans$ 和 $ans_d$ 的值。

Input

第一行输入一个整数 $T\ (1\le T\le 10^3)$，代表接下来有 $T$ 组数据。

对于每组数据，第一行一个整数 $n\ (3\le n\le 10^5)$，表示数组长度。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n\ (1\leq a_i\leq 10^6)$，表示这个数组。

对于所有数据，满足 $\sum n\le 10^5$。

Output

对于每组数据输出一行两个整数，分别表示 $ans$ 和 $ans_d$，两整数之间用一个空格隔开。

Samples

3
3
1 2 4
6
1 1 1 1 1 1
9
1 1 1 2 2 2 4 4 4

1 0
120 0
45 0

Note

对于样例 $3$，当公比大于 $1$ 时，其中 $i$ 可以从下标集合 $\{1,2,3\}$ 选择，$j,k$ 同理可以分别从 $\{4,5,6\},\{7,8,9\}$ 选择当公比等于 $1$ 时，$i,j,k$ 可以在各自相同的数中选取三元组。比如三元组 $(1,2,3),(1,3,2)$，均计算一次答案，总答案即为 $3\times 3\times 2+3^3=45$。

Resources

电子科技大学第十四届 ACM 趣味程序设计竞赛