当前没有测试数据。

题目描述

最近，K1o0n 一时冲动买下了 $n$ 包茶叶，现在他想知道什么时候才能试完所有的调配方案。他对茶叶十分挑剔，于是立刻给每一包茶设定了一个风味强度：整数 $a_i$。

茶包按照购买顺序摆在架子上，K1o0n 懒得重新排序：泡茶时，他按顺序将前 $j$ 包全部倒入茶壶，再额外从第 $i$ 包中舀一勺加入。我们将这种调配方案记作 $(i,j)$，它的风味强度定义为所有倒入茶壶的茶叶强度的乘积：

$$F(i, j) = a_i \cdot \prod_{k=1}^{j} a_k = a_i \cdot \left(a_1 \cdot a_2 \cdot \ldots \cdot a_j\right)$$

K1o0n 将泡好的茶分到若干个完全相同的杯子中：当且仅当 $d$ 是 $F(i,j)$ 的正约数时，他可以分成 $d$ 杯，且每杯分到的茶量相等。如果一个调配方案对应的合法 $d$ 的数量是奇数，就称这个调配方案是“多变的”。

请统计 K1o0n 一共可以调出多少个“多变的”调配方案，即满足 $1 \le i \le n$、$1 \le j \le n$，且 $F(i,j)$ 的正约数个数为奇数的有序对 $(i,j)$ 的数量。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），代表茶包的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），代表每包茶叶的风味强度。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试用例，输出一个整数：“多变的”调配方案的总数。

请注意答案可能无法存入 32 位整数，请使用 64 位整型（C++ 中为 long long，Java 中为 long）。

4
4
2 3 6 4
4
974153 980051 988027 1
8
12 3 5 45 1 7 63 2
1
13

4
4
11
1

原题链接

原题链接