题目描述

给定一个字符串$s=s_1s_2…s_n$，长度为 $n$，其中每个字符都是数字 $1、2、...、9$。

字符串 $s[l…r]$ 是 $s$ 的一个子串，表示为 $s_ls_{l+1}…s_r$。一个子串 $s[l…r]$被称为“偶数子串”，当且仅当它所表示的数字是偶数（例如在“$123$”中，子串“$12$”是一个“偶数子串”）。

现在，请计算字符串 $s$ 中所有偶数子串的数量。注意，即使某些子串内容相同，但它们的起始位置和结束位置不同，仍然会被视为不同的子串。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 500$)，表示字符串 $s$ 的长度。 第二行包含一个字符串 $s$，长度为 $n$，该字符串只包含数字 $1、2、...、9$。

输出格式

输出一个整数，表示字符串 $s$ 中偶数子串的数量。

样例

4
1234

6

4
2244

10

提示

在第一个示例中，字符串为 1234，它的所有子串如下：

• 区间 $[1,1]$，子串为 1，不是偶数子串；

• 区间 $[1,2]$，子串为 12，是偶数子串；

• 区间 $[1,3]$，子串为 123，不是偶数子串；

• 区间 $[1,4]$，子串为 1234，是偶数子串；

• 区间 $[2,2]$，子串为 2，是偶数子串；

• 区间 $[2,3]$，子串为 23，不是偶数子串；

• 区间 $[2,4]$，子串为 234，是偶数子串；

• 区间 $[3,3]$，子串为 3，不是偶数子串；

• 区间 $[3,4]$，子串为 34，是偶数子串；

• 区间 $[4,4]$，子串为 4，是偶数子串。

因此，偶数子串的数量为 $6$。