我们将数组中的 $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) 定义为在数组中至少出现两次的最大数字。具体来说,如果没有至少出现两次的数字,则 $$$\operatorname{MAD}$$$ 值为 $$$0$$$。
例如,$$$\operatorname{MAD}([1, 2, 1]) = 1$$$, $$$\operatorname{MAD}([2, 2, 3, 3]) = 3$$$, $$$\operatorname{MAD}([1, 2, 3, 4]) = 0$$$。
给你一个大小为 $$$n$$$ 的数组 $$$a$$$。最初,变量 $$$sum$$$ 设置为 $$$0$$$。
以下过程将按顺序循环执行,直到 $$$a$$$ 中的所有数字都变为 $$$0$$$:
1. 设置 $$$sum := sum + \sum_{i=1}^{n} a_i$$$;
2. 令 $$$b$$$ 为大小为 $$$n$$$ 的数组。为所有 $$$1 \le i \le n$$$ 设置 $$$b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])$$$,然后为所有 $$$1 \le i \le n$$$ 设置 $$$a_i := b_i$$$。
求处理后$$$sum$$$的值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。
对于每个测试用例:
- 第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的大小;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在新行中输出 $$$sum$$$ 的值。
示例
输入 #1
4 1 1 3 2 2 3 4 2 1 1 2 4 4 4 4 4
输出 #1
1 13 9 40
注意
在第一个测试用例中,最初 $$$a=[1]$$$。
在第一个循环中:
1. 设置 $$$sum := sum + a_1 = 0+1=1$$$;
2. 设置$$$b_1 :=\\operatorname{MAD}([a_1])=\\operatorname{MAD}([1])=0$$$,然后设置$$$a_1 := b_1$$$。
在第一个循环之后,$$$a=[0]$$$ 并且过程结束。处理后$$$sum$$$的值为$$$1$$$。
在第二个测试用例中,最初 $$$a=[2,2,3]$$$。
第一个循环之后,$$$a=[0,2,2]$$$ 和 $$$sum=7$$$。
第二次循环后,$$$a=[0,0,2]$$$ 和 $$$sum=11$$$。
第三次循环后,$$$a=[0,0,0]$$$ 和 $$$sum=13$$$。然后该过程结束。
处理后$$$sum$$$的值为$$$13$$$。