题目描述

小可可和小多在研究数字串，他们在研究一个数字串的所有子串。

给定一个长为 N 的数字串（即由若干 0 ∼ 9 的数字构成的字符串），请你回答有 多少连续子串（即从该串中选出连续的若干个数字，可以包括前导 0）是 3 的倍数 。

输入

第一行一个正整数 $N$，代表数字串的长度。

第二行一个长为 $N$ 的数字串。

输出

一行一个正整数，代表满足条件的子串数目。

样例

5
04321

6

【样例 1 解释】 6个满足条件的串分别为 0, 0432, 432, 3, 321, 21。

数据规模与约定

对于 50% 的数据，满足 1 ≤ N ≤ 1000。

对于 100% 的数据，满足 1 ≤ N ≤ 5000。