Type: Default 1000ms 256MiB

幸运区间

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

为什么幸运数非得是 7 呢?

2,3,4,5,6为啥就不行呢……

在古老的传统中,数字 $7$ 被视为幸运的象征。一个正整数若能整除 $7$,便被认为是“幸运数”。

现在,你得到了一个长度为 $n$ 的数字符串 $s$。你需要统计有多少个区间 $[l, r]$($1 \le l \le r \le n$),使得子串 $s[l \ldots r]$ 构成的十进制整数是 $7$ 的倍数。

例如,对于 $s = 14007$,子串 “$14007$” 构成整数 $14007$,是 $7$ 的倍数;子串 “$7$” 构成整数 $7$,也是 $7$ 的倍数;子串 “$007$” 构成整数 $7$,同样是 $7$ 的倍数;字串 “$0$” 也是 $7$ 的倍数。

Input Format

第一行一个整数 $T$($1 \le T \le 10^3$),表示测试数据组数。

对于每组数据:

$\quad$ 1. 第一行一个整数 $n$($1 \le n \le 10^6$)。

$\quad$ 2. 第二行一个长度为 $n$ 的字符串 $s$,仅包含数字 $0 \sim 9$。

保证所有测试数据的 $\sum n \le 10^6$。

Output Format

对于每组测试数据,输出一行一个整数,表示满足条件的区间对数。

2
5
14007
3
777
10
6

Hint

对于第一组数据 $s = 14007$,共有 $10$ 个满足条件的区间:

$[1,2],[1,3],[1,4],[1,5],[3,3],[3,4],[3,5],[4,4],[4,5],[5,5]$。