每天 Codehorses 上都会发布一道新的编程题。因此，在接下来的 $n$ 天里将发布 $n$ 道题：第 $i$ 天发布的题目难度为 $a_i$。

Polycarp 想要选择恰好三天 $i$、$j$ 和 $k$（$i < j < k$），使得第 $j$ 天和第 $i$ 天的难度差等于第 $k$ 天和第 $j$ 天的难度差。换句话说，Polycarp 希望等式 $a_j - a_i = a_k - a_j$ 成立。

求 Polycarp 以期望的方式选择这三天的可能方案数。

输入格式

第一行包含一个整数 $t$ —— 输入中测试数据的组数（$1 \le t \le 10$）。接下来是 $t$ 组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$ —— 天数（$3 \le n \le 2000$）。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是第 $i$ 天题目的难度（$1 \le a_i \le 10^9$）。

输出格式

输出 $t$ 个整数 —— 按输入顺序对应每组测试数据的答案。每组测试数据的答案是满足 $1 \le i < j < k \le n$ 且 $a_k - a_j = a_j - a_i$ 的三元组下标 $(i, j, k)$ 的数量。

样例

输入样例 1

4
5
1 2 1 2 1
3
30 20 10
5
1 2 2 3 4
9
3 1 4 1 5 9 2 6 5

输出样例 1

1
1
4
5