CF2004F.Make a Palindrome

给定一个由 $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$ 值之和。

由 ChatGPT 4.1 翻译