题目描述

给定一个数组 $a$ ，包含 $n$ 个正整数。Alice 和 Bob 将用该数组进行一个游戏，Alice 先手，双方交替进行操作。

在每一次回合中，当前玩家必须选择一个值 $x>0$，且该值在当前数组 $a$ 中至少出现一次。然后执行以下操作：

• 当前玩家获得与数组中值等于 $x$ 的元素个数相等的分数（每个等于 $x$ 的元素计 $1$ 分）；
• 数组中所有值为 $x$ 的元素都减 $1$，变为 $x-1$。

注意只有当前数组中存在值 $x$ 时玩家才能选择该 $x$，因此每一次有效操作都会得到正分。游戏在数组所有元素都变为 $0$ 时结束（此时无法再选择任何 $x$）。

假设两名玩家都以最大化自己得分为目标并且都最优地进行游戏，求游戏结束时 Alice 和 Bob 各自得到的分数。

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 10^3$）——测试用例个数。随后为 $t$ 个测试用例。

每个测试用例格式如下：

第一行包含一个整数 $n$（$1\le n\le 2\cdot10^5$）——数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$）——数组元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例，输出一行，包含两个整数：Alice 和 Bob 在双方均最优的情况下最终得到的分数（用空格分隔）。

样例输入

3
3
2 1 1
5
3 3 3 5 5
4
9 9 9 9

样例输出

3 1
10 9
20 16

说明

样例解释

在第一个样例中，Alice 首先选择 $x=1$，把两个 $1$ 减为 $0$，获得 $2$ 分；之后 Bob 只能选 $x=2$，获得 $1$ 分；接着 Alice 再选 $x=1$（剩下的 $2$ 变为 $1$）获得 $1$ 分，最终 Alice $3$ 分，Bob $1$ 分。