P14585 [LNCPC 2025] Entering the unknown

$\text{Entering the unknown,}$ $\text{Sending all the poets to the stars,}$ $\text{Daring to see beyond the manmade,}$ $\text{Woe to you who evade the horizon.}$ $\text{——Capoo}$ 

给定一个长度为 $n$ 的正整数数组，请您求出有多少个非空子数组 $^{\text{*}}$ 满足：该非空子数组的正整数之和能被出现在该非空子数组中的最大**数字** $^{\text{†}}$ 整除。 --- $^{\text{*}}$ 一个数组 $a$ 是一个数组 $b$ 的非空子数组，当且仅当 $a$ 可以通过从 $b$ 的开头删除零个或者多个数以及从结尾删除零个或者多个数而得到，并且 $a$ 含有至少一个数。 $^{\text{†}}$ 数字（digit）是指构成数（number）的 $0,1,2,3,4,5,6,7,8,9$。例如，出现在数组 $[213]$ 中的数字有 $1,2,3$，最大数字是 $3$；出现在数组 $[2025,11,15]$ 中的数字有 $0,1,2,5$，最大数字是 $5$。

每个测试点包含多组测试数据。第一行给定一个整数 $T(1 \le T \le 10^4)$，表示测试数据组数。 对于每组测试数据： 第一行给定一个整数 $n(1\le n\le 10^5)$，表示数组长度。 第二行给定 $n$ 个正整数 $x_1,x_2,\ldots,x_n$（$1\le x_i\le 10^9$），表示数组。 保证在每个测试点中所有测试数据的 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一行一个整数，表示满足题目要求的非空子数组的数量。

对于样例的第一组测试数据，非空子数组一共有 $6$ 个： 对于非空子数组 $[213]$，正整数之和是 $213$，出现的最大数字是 $3$，$213$ 能被 $3$ 整除，满足题目要求。 对于非空子数组 $[12]$，正整数之和是 $12$，出现的最大数字是 $2$，$12$ 能被 $2$ 整除，满足题目要求。 对于非空子数组 $[21]$，正整数之和是 $21$，出现的最大数字是 $2$，$21$ 不能被 $2$ 整除，不满足题目要求。 对于非空子数组 $[213,12]$，正整数之和是 $213+12=225$，出现的最大数字是 $3$，$225$ 能被 $3$ 整除，满足题目要求。 对于非空子数组 $[12,21]$，正整数之和是 $12+21=33$，出现的最大数字是 $2$，$33$ 不能被 $2$ 整除，不满足题目要求。 对于非空子数组 $[213,12,21]$，正整数之和是 $213+12+21=246$，出现的最大数字是 $3$，$246$ 能被 $3$ 整除，满足题目要求。 因此，满足题目要求的非空子数组的数量是 $4$。