Prof. Pang 最近组建了他著名的编程团队。为了在 ICPC 中追求金牌，数百名学生加入了他的团队。不幸的是，Prof. Pang 的一名学生认为对于任何整数 $a$ 和 $b$，都有 $a \times b \ge a + b$。为了反驳这个命题，Prof. Pang 在纸上写下了 $n$ 个数 $a_1, a_2, \dots, a_n$，并希望你计算有多少对数字 $(a_i, a_j)$ ($1 \le i < j \le n$) 满足 $a_i \times a_j < a_i + a_j$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行包含答案。

样例

输入格式 1

2
8
3 -1 4 1 -5 9 2 -6
1
0

输出格式 1

19
0