题目背景

$\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$。

输出格式

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

2
3
213 12 21 
7
314 880 246 170 493 474 129 

4
7

提示

对于样例的第一组测试数据，非空子数组一共有 $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$。