给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
让函数 $$$f(b)$$$ 返回使数组 $$$b$$$ 成为回文所需的最少操作数。您可以进行的操作有:
- 选择两个相邻元素 $$$b_i$$$ 和 $$$b_{i+1}$$$,删除它们,并将它们替换为等于 $$$(b_i + b_{i + 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 \left(\sum_{1 \le l \le r \le n}{f(a[l..r])}\right)$$$,其中 $$$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$$$ 的值之和。
示例
输入 #1
4 3 2 1 3 4 1 1 1 1 5 4 2 3 1 5 4 1 2 1 2
输出 #1
3 0 14 5