A-Arithmetic Progression_2021牛客暑期多校训练营2

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Le Le loves sequences, so El El gives him one as present days ago.

Le Le treasures the sequence ${a}$ , and everyday he will do the following as routine:

Choose a subsequence $a_l,a_{l+1}\cdots ,a_{r}$ , create a new sequence b, and let $b_{i-l+1}=a_i(l\leq i \leq r)$ .
Sort $b_1,b_2,\cdots ,b_{r-l+1}$ increasingly.

For he takes arithmetic progressions as the most beautiful sequences in the world, he wonders how many ways to choose the subsequence so that ${b}$ could be an arithmetic progression.

An arithmetic progression is a sequence $a_1,a_2,\cdots ,a_n$ that $\forall 1<i<n, 2a_i=a_{i-1}+a_{i+1}$ .

输入描述:

The first line contains an integer  — number of test cases.

Each test case contains two lines:

The first line contains an integer , denoting the length of the sequence.

The second line contains  integers .

输出描述:

Output  lines containing the number of possible subsequences for each test case.

示例1

输入

复制

1
6
1 4 3 2 5 7

输出

复制

备注:

.

For each test case, it's guaranteed that  and all  are distinct.