F. 构造回文
时间限制：每个测试点 $5$ 秒
内存限制：$512$ 兆字节

给你一个由 $n$ 个整数组成的数组 $a$。

定义函数 $f(b)$ 为将数组 $b$ 变成回文所需的最少操作次数。允许的操作有：

• 选择相邻的两个元素 $b_i$ 和 $b_{i+1}$，删除它们，并用一个等于 $(b_i + b_{i+1})$ 的元素替换它们；
• 或者选择一个大于 $1$ 的元素 $b_i > 1$，删除它，并用两个正整数 $x$ 和 $y$（$x > 0$，$y > 0$）替换它，使得 $x + y = b_i$。

例如，从数组 $b = [2,1,3]$ 出发，可以通过一次操作得到以下数组：$[1,1,1,3]$、$[2,1,1,2]$、$[3,3]$、$[2,4]$ 或 $[2,1,2,1]$。

请计算 $\displaystyle \sum_{1 \le l \le r \le n} f(a[l..r])$，其中 $a[l..r]$ 表示数组 $a$ 中从下标 $l$ 到下标 $r$ 的子数组。换句话说，求出数组 $a$ 的所有子数组的 $f$ 值之和。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）。

附加输入限制：所有测试用例的 $n$ 之和不超过 $2000$。

输出格式
对于每个测试用例，输出一个整数——数组 $a$ 的所有子数组的 $f$ 值之和。

样例输入

4
3
2 1 3
4
1 1 1 1
5
4 2 3 1 5
4
1 2 1 2

样例输出

3
0
14
5