Nanarikom 在绘制折线图。
Nanarikom 的折线图包含 nn 个数据点。数据点的横坐标分别为 1, 2, \dots, n1,2,…,n，纵坐标分别为 a_1, a_2, \dots, a_na1,a2,…,an。
现在，Nanarikom 想知道，有多少横坐标区间 [l, r][l,r] 满足 1 \leq l \leq r \leq n1≤l≤r≤n，且使得折线图在区间内的部分是中心对称的。特别地，我们认为 l = rl=r 的区间总是中心对称的。
你需要回答 Nanarikom 的 TT 组询问。
第一行包含一个整数 TT（1 \leq T \leq 10^61≤T≤106），代表测试数据组数。对于每组测试数据：
输入数据保证 \sum n \leq 10^6∑n≤106。
1
5
1 3 5 2 411