Вам дана строка \(s=s_1s_2\dots s_n\) длины \(n\), содержащая только цифры \(1\), \(2\), ..., \(9\).
Подстрокой \(s[l \dots r]\) строки \(s\) назовём строку \(s_l s_{l + 1} s_{l + 2} \ldots s_r\). Подстрока \(s[l \dots r]\) строки \(s\) называется чётной, если число, которое соответствует этой подстроке является чётным.
Найдите количество чётных подстрок строки \(s\). Обратите внимание, что если некоторые подстроки равны как строки, но определены разными числами \(l\), \(r\), то они считаются различными.
Выходные данные
Выведите одно целое число — количество чётных подстрок в строке \(s\).
Примечание
В первом примере следующие \([l, r]\) пары задают чётные подстроки:
- \(s[1 \dots 2]\)
- \(s[2 \dots 2]\)
- \(s[1 \dots 4]\)
- \(s[2 \dots 4]\)
- \(s[3 \dots 4]\)
- \(s[4 \dots 4]\)
Во втором примере, все \(10\) подстрок строки \(s\) являются чётными. Обратите внимание, что не смотря на то, что строки \(s[1 \dots 1]\) и \(s[2 \dots 2]\) задают подстроку «2», они всё равно считаются как различные подстроки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1234
|
6
|
|
2
|
4
2244
|
10
|