You are given a string $s=s_1s_2\dots s_n$ of length $n$, which only contains digits $1$, $2$, ..., $9$.

A substring $s[l \dots r]$ of $s$ is a string $s_l s_{l + 1} s_{l + 2} \ldots s_r$. A substring $s[l \dots r]$ of $s$ is called even if the number represented by it is even. 

Find the number of even substrings of $s$. Note, that even if some substrings are equal as strings, but have different $l$ and $r$, they are counted as different substrings.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 65000$) — the length of the string $s$.

The second line contains a string $s$ of length $n$. The string $s$ consists only of digits $1$, $2$, ..., $9$.


-----Output-----

Print the number of even substrings of $s$.


-----Examples-----
Input
4
1234

Output
6
Input
4
2244

Output
10


-----Note-----

In the first example, the $[l, r]$ pairs corresponding to even substrings are:   $s[1 \dots 2]$

 $s[2 \dots 2]$

 $s[1 \dots 4]$

 $s[2 \dots 4]$

 $s[3 \dots 4]$

 $s[4 \dots 4]$ 

In the second example, all $10$ substrings of $s$ are even substrings. Note, that while substrings $s[1 \dots 1]$ and $s[2 \dots 2]$ both define the substring "2", they are still counted as different substrings.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = input()
r = 0
for i in range(n):
    if s[i] in '2468':
        r += i + 1
print(r)

rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

def solve(N, S):
    ans = 0
    for i,x in enumerate(S):
        x = int(x)
        if x%2 == 0:
            ans += i + 1
    return ans


for tc in range(1):#rri()):
    N = rri()
    S = rr()
    print(solve(N, S))


n = int(input())
s = input()
ans = 0
for i in range(n):
    if int(s[i]) % 2 == 0:
        ans += i + 1
print(ans)

n = int(input())
s = list(input())
s = list(map(int, s))
cnt = 0
for i in range(n):
    if s[i] % 2 == 0:
        cnt += i + 1
print(cnt)

import math
import bisect

def argsort(ls):
    return sorted(range(len(ls)), key=ls.__getitem__)

def f(p=0):
    if p==0:
        return int(input())
    if p==1:
        return map(int, input().split())
    elif p==2:
        return list(map(int, input().split()))
    else:
        return sorted(list(map(int, input().split())))


n = f()
s = input()
sm = 0
for i in range(n):
    if int(s[i])%2==0:
        sm+=i+1

print(sm)

n = int(input())
s = input()

total = 0
for i,x in enumerate(s):
    if x in "02468":
        total += i+1
print (total)

r = 0
n = int(input())
s = input()
for i in range(n):
        if int(s[i]) % 2 == 0:
                r += i + 1

print(r)


n = int(input())
s = input()
k = 0
for i in range(1, n + 1):
	d = int(s[i - 1])
	if d % 2 == 0:
		k += i
print(k)


import math
import string
import re
import math
import random
from decimal import Decimal, getcontext


def ria():
    return [int(i) for i in input().split()]


n = ria()[0]
st = input()
rs=0
for i in range(n):
    if int(st[i])%2==0:
        rs+=i+1
print(rs)


n = int(input().strip())
s = input().strip()
ans = 0
for i in range(len(s)):
	if int(s[i])%2 == 0:
		ans += i+1
print(ans)

input()
S = list(map(int,list(input())))
an = 0

for i in range(len(S)):
    if S[i] % 2 == 0:
        an += i + 1
print(an)        


n = int(input())
u = list(map(int, list(input())))
ans = 0
for i in range(n):
    if u[i] % 2 == 0:
        ans += i + 1
print(ans)


n = int(input())
s = input()
num = 0
for i in range(n):
    if int(s[i]) % 2 == 0:
        num += i+1
print(num)


n=int(input())
s=input()
r=0
for i in range(n):
    if int(s[i])%2==0:
        r+=i+1
print(r)


import math
import bisect
import itertools
import sys
I=lambda : sys.stdin.readline()
mod=10**9 +7
'''fact=[1]*100001
ifact=[1]*100001
for i in range(1,100001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''

def modu(a,m):
    if a%m:
        return a%m
    return m

def mindiff(a):
    b=a[:]
    b.sort()
    m=10000000000
    for i in range(len(b)-1):
        if b[i+1]-b[i]<m:
            m=b[i+1]-b[i]
    return m
    
def lcm(a,b):
    return a*b//math.gcd(a,b)

    
def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
def is_prime(num):
    if num == 1: return False
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True
    
  
def ceil(a,b):
    if a%b==0:
        return a//b
    else:
        return (a//b + 1)


def ncr1(n,r):
    s=1
    for i in range(min(n-r,r)):
        s*=(n-i)
        s%=mod
        s*=pow(i+1,mod-2,mod)
        s%=mod
    return s


#/////////////////////////////////////////////////////////////////////////////////////////////////

n=int(input())
s=input()
ans=0
for i in range(n):
    if s[i] in ['2','4','6','8']:
        ans+=i+1
print(ans)        


n = int(input())
s=input()
ans = 0
for i in range(n):
    if s[i] in '02468':
        ans += i+1
print(ans)

import math
import random
import sys
from collections import defaultdict as dd
ans = 0
n = int(input())
l = [int(i) for i in input()]
for i in range(n):
    if l[i] % 2 == 0:
        ans += (i + 1)
print(ans)



n = int(input())
s = input()
res = 0
for i in range(n):
    if int(s[i]) % 2 == 0:
        res += i + 1
print(res)

n = int(input())
seq = input()
nbPaires = 0
for i in range(n):
	if int(seq[i])%2 == 0:
		nbPaires += i+1
print(nbPaires)

n=int(input())
s=input()
ans=0
for i in range(n):
         if(int(s[i])%2==0):
                  ans+=i+1
print(ans)

import io, sys, atexit, os

import math as ma
from decimal import Decimal as dec
from itertools import permutations


def li ():
	return list (map (int, input ().split ()))


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


mm = 1000000007


def solve ():
	t = 1
	for it in range (t):
		n=nu()
		a=input()
		cc=0
		for i in range(n):
			if(int(a[i])%2==0):
				cc+=i+1
		print(cc)



def __starting_point():
	solve ()
__starting_point()

n = int(input())
s = input()
a = 0
for i in range(len(s)):
    if int(s[i])%2 == 0:
        a += (i+1)
print(a)


n = int(input())
s = input()
ans = 0
for i in range(n):
    if int(s[i])%2 == 0:
        ans+=i+1
print(ans)

def mp():
    return map(int, input().split())

n = int(input())
s = input()
cnt = 0

for i in range(n):
    if int(s[i]) % 2 == 0:
        cnt += i + 1

print(cnt)