该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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