Migrated from Lutece 2993 How Many Triangles!

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

春天来了，$xxxl$ 在清水河畔捡到了 $12$ 根树枝，树枝编号从 $1$ 到 $12$，他想知道用这12根树枝最多可以拼出多少个三角形。

为了简化问题，每一根树枝可以被视为长度一定的线段。现在给出 $12$ 根树枝的长度，请问在每根木棍最多只能参与到一个三角形的组成的前提下，最多可以拼出几个三角形。同时 $xxxl$ 也想知道有多少种不同的方案可以组成这么多的三角形。

注意：两种方案被视为不同，当且仅当两种方案中组成某两个三角形的树枝编号不一样。

Input

第一行一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行输入 $12$ 个正整数，表示这些木棍的长度。

Output

输出 $T$ 行，每行两个整数，第一个数表示最多可以组成三角形的个数，第二个数表示有多少种方案可以组成这么多的三角形。

Samples

5
1 1 4 5 1 4 1 9 1 9 8 1
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 5 8 13 21 34 55 89 144 233
2 3 6 15 27 59 72 83 121 159 201 234
2 2 4 8 16 32 64 128 256 512 1024 1281

4 30
3 2063
0 1
2 59
1 1

Constraints

$1\leq T \leq 4000$，木棍的长度 $len_i$ 满足 $1\leq len_i \leq 2 \times10^9$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming