import sugar
template exit* = quit 0
template write*( v :varargs[untyped] ) = stdout.write v
type Bool* = bool
type Int* = int
type Char* = char
type String* = string
type Interval = HSlice[Int,Int]


####################
###   operator   ###
####################
proc less*[T](x,y:T):Bool = x > y
proc more*[T](x,y:T):Bool = x < y
proc plus*[T](x,y:T):T = x + y
proc times*[T](x,y:T):T = x * y

proc less*[T](x:T):proc(y:T):Bool = return proc(y:T):Bool = x > y
proc more*[T](x:T):proc(y:T):Bool = return proc(y:T):Bool = x < y
proc plus*[T](y:T):proc(x:T):T = return proc(x:T):T = x + y
proc times*[T](y:T):proc(x:T):T = return proc(x:T):T = x * y


####################
###   template   ###
####################
template Make*(body :untyped) :auto =
    let f = proc() :auto = body
    f()

template Sum*(body:untyped) :auto =
    iterator it() :auto = body
    var ans = 0
    for x in it(): ans += x
    ans

template Max*(body:untyped) :Int =
    iterator it() :Int = body
    var ans = Int.low
    for x in it(): ans.max= x
    ans

template Min*(body:untyped) :Int =
    iterator it() :Int = body
    var ans = Int.high
    for x in it(): ans.min= x
    ans

template All*(body:untyped) :Bool =
    iterator it() :Bool = body
    var ans = true
    for x in it():
        if not x:
            ans = false
            break
    ans

template Any*(body:untyped) :Bool =
    iterator it() :Bool = body
    var ans = false
    for x in it():
        if x:
            ans = true
            break
    ans


####################
###   iterator   ###
####################
iterator items*(p :(Int,Int,Int)) :Int =
    let (l,r,n) = p
    var i = l
    while i < r:
        yield i
        i += n

iterator items*( p :(Int,Int) ) :Int =
    let (L,R) = p
    for i in L..<R:
        yield i

iterator items*( N :Int ) :Int =
    for i in 0..<N:
        yield i

iterator infty*() :Int =
    var i=0
    while true:
        yield i
        i.inc

iterator reverse*( L, R :Int ) :Int =
    var i = R
    while i > L:
        i.dec
        yield i

iterator reverse*( N :Int ) :Int =
    for i in reverse(0, N):
        yield i


################
###   Vect   ###
################
type Vect[T] = seq[T]
proc `$`[T]( v :Vect[T] ) :String =
    for x in v: result &= $x & ' '
proc vect*[T]( n :Int ): Vect[T] =
    newSeq[T]( result, n )
proc vect*[T]( N :Int; X :T ) :Vect[T] =
    result = vect[T] N
    for i in N:
        result[i] = X
proc vect*[T]( S :openArray[T] ) :Vect[T] =
    result = vect[T] S.len
    for i, e in S:
        result[i] = e
proc vect*[T](n :Int, f :proc(i:Int):T) :Vect[T] =
    result = vect[T] n
    for i in n: result[i] = f(i)
proc runLength[T](v :openarray[T]) :Vect[(T,Int)] =
    result = vect[(T,Int)] []
    var now :T = v[0]
    var cnt = 1
    for x in v[1..<v.len]:
        if now == x:
            cnt.inc
        else:
            result.push (now,cnt)
            now = x
            cnt = 1
    result.push (now,cnt)
proc elem[T](v :openarray[T], a :T) :Bool =
    for x in v:
        if x == a: return true
    return false
proc arg*[T](v :openarray[T], a :T) :Int =
    for i, x in v:
        if x == a: return i
    return v.len
proc push*[T]( V :var Vect[T]; X :T ) =
    V.setLen(V.len+1)
    V[V.len-1] = X
proc countIf*[T]( S :openarray[T], f :proc(x:T):Bool ) :Int =
    for e in S:
        if f(e):
            result.inc
proc map*[X,Y](v :openarray[X], f :proc(x:X):Y) :Vect[Y] =
    result = vect[Y] v.len
    for i in v.len: result[i] = f(v[i])
proc reverse*[T](v :openarray[T]) :Vect[T] =
    result = vect[T] v.len
    for i in v.len:
        result[v.len-i-1] = v[i]
converter toVect(s :String) :Vect[Char] =
    for c in s: result.push c
proc full*[T](s :openarray[T], x :T) :Vect[T] =
    result = vect[T] s.len
    for i in s.len: result[i] = x
proc `full=`*[T](s :var Vect[T], x :T) =
    for i in s.len: s[i] = x
proc cumulative*[T](v :openarray[T]) :Vect[T] =
    result = vect[T] v.len + 1
    if v.len == 0: return
    for i in v.len: result[i+1] = result[i] + v[i]
proc sum[T](v :openarray[T]) :T =
    for x in v: result = result + x

proc dim[T](a :openarray[T]) :Int =
    for i in a.len.reverse:
        if a[i] != 0: return i
    return -1
proc normalization[T](a :var Vect[T]) =
    a.setLen a.dim+1
proc `+`*[T](a, b :openarray[T]) :Vect[T] =
    result = vect[T] max(a.len,b.len)
    for i in max(a.len,b.len):
        if i < a.len: result[i] += a[i]
        if i < b.len: result[i] += b[i]
    result.normalization
proc `-`*[T](a, b :openarray[T]) :Vect[T] =
    var c = vect[T] b.len
    for i in b.len: c[i] = -b[i]
    return a + c
proc `*`*[T](a, b :openarray[T]) :Vect[T] =
    result = vect[T] a.len + b.len - 1
    for i in a.len:
        for j in b.len:
            result[i+j] += a[i]*b[j]
    result.normalization
proc `div`*[T](a, b :openarray[T]) :Vect[T] =
    result = vect[T] a.dim+1 - b.dim
    var t = vect[T] a
    for i in reverse(b.dim, a.dim+1):
        if t[i] mod b[b.dim] != 0: return
        result[i-b.dim] = t[i] div b[b.dim]
        for j in b.dim+1:
            t[i+j-b.dim] -= b[j] * result[i-b.dim]
proc `mod`*(a, b :openarray[Int]) :Vect[Int] =
    result = vect[Int] a
    var t = vect[Int] a.dim+1 - b.dim
    for i in reverse(b.dim, a.dim+1):
        if result[i] mod b[b.dim] != 0: return
        t[i-b.dim] = result[i] div b[b.dim]
        for j in b.dim+1:
            result[i+j-b.dim] -= b[j] * t[i-b.dim]
    result.normalization



################
###   tens   ###
################
type Tens[T] = object
    data :Vect[T]
    shape :Vect[Int]

proc tens*[T]( S :varargs[Int] ) :Tens[T] =
    var N :Int = 1
    for s in S: N *= s
    result.data = vect[T](N)
    result.shape = @S

proc `[]`[T]( t :Tens[T], s :varargs[Int] ) :T =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    return t.data[n]

proc `[]=`[T]( t :var Tens[T], s :varargs[Int], e :T ) =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    t.data[n] = e

proc `full=`*[T]( S :var Tens[T]; X :T ) =
    for i in S.data.len: S.data[i] = X

iterator items[T]( t :Tens[T] ) :T =
    for x in t.data: yield x



#####################
###   algorithm   ###
#####################
type IndexDefect = object of Defect
proc upperBound*(i :Interval; p :proc(i:Int):Bool) :Int =
    var (ok, ng) = (i.a-1, i.b+1)
    while ng - ok > 1:
        let mid = (ng + ok) div 2
        if p(mid): ok = mid
        else: ng = mid
    if ok < i.a: raise new IndexDefect
    return ok

proc upperBound*[T](v :Vect[T], x :T) :Int =
    upperBound(0..<v.len) do (i:Int)->Bool: v[i] <= x

proc lowerBound*(i :Interval; p :proc(i:Int):Bool) :Int =
    var (ng, ok) = (i.a-1, i.b+1)
    while ok - ng > 1:
        let mid = (ng + ok) div 2
        if p(mid): ok = mid
        else: ng = mid
    if ok > i.b: raise new IndexDefect
    return ok

proc lowerBound*[T](v :Vect[T]; x :T) :Int =
    lowerBound(0..<v.len) do (i:Int)->Bool: v[i] >= x

iterator shakutori*(n,m :Int, p :(Int,Int) -> Bool) :(Int,Int) =
    var s = n
    while s < m:
        let t = upperBound(s..m, (i:Int) => p(s,i))
        if t - s == n:
            s.inc
        else:
            yield (s,t)
            s = t

proc doubling*[T](a :T, n :Int, f :proc(x,y:T):T) :T =
    result = a
    var (a,n) = (a,n-1)
    while true:
        if n mod 2 == 1:
            result = f(result,a)
        if n <= 1: break
        a = f(a,a)
        n.div= 2



####################
###   Priority   ###
####################
type Priority[T] = object
    data :Vect[T]
    compare :proc(x,y:T):bool
proc priority*[T]() :Priority[T] =
    result.data = vect[T](1)
    result.compare = proc(x,y:T):bool = x < y
proc priority*[T]( compare :proc(x,y:T):bool ) :Priority[T] =
    result.data = vect[T](1)
    result.compare = compare
proc exist[T]( p :Priority[T] ) :bool = p.data.len > 1
proc push[T]( p :var Priority[T], e :T ) =
    var n = p.data.len
    p.data.add(e)
    while n div 2 != 0 and p.compare( p.data[n], p.data[n div 2] ):
        swap( p.data[n], p.data[n div 2] )
        n = n div 2
proc priority*[T](v :openarray[T]) :Priority[T] =
    result = priority[T]()
    for x in v: result.push x
proc front[T]( p :Priority[T] ) :T = p.data[1]
proc trash[T]( p :var Priority[T] ) =
    let N = p.data.len - 1
    p.data[1] = p.data[N]
    p.data.setLen(N)
    var n = 1
    while true:
        if n * 2 >= N: break
        if n * 2 + 1 >= N:
            if p.compare( p.data[n], p.data[n * 2] ): break
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
            continue
        if not p.compare( p.data[n * 2], p.data[n] ) and
           not p.compare( p.data[n * 2 + 1], p.data[n] ):
            break
        if p.compare( p.data[n * 2], p.data[n * 2 + 1] ):
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
        else:
            swap( p.data[n], p.data[n * 2 + 1] )
            n = n * 2 + 1
proc pop[T]( p :var Priority[T] ) :T =
    result = p.front
    p.trash


#################
###   coord   ###
#################
type Coord* = tuple[x:int,y:int]
proc `+`[A,B](a,b :(A,B)) :(A,B) = (a[0]+b[0], a[1]+b[1])
proc `-`[A,B](a,b :(A,B)) :(A,B) = (a[0]-b[0], a[1]-b[1])
proc `*`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0]*b, a[1]*b)
proc `div`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0] div b, a[1] div b)
proc `mod`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0] mod b, a[1] mod b)
proc elem(i :Interval, n :Int) :Bool =
    if i.a <= n and n <= i.b: true
    else: false

##################
###   number   ###
##################
proc `mod`(a,b :Int) :Int =
    result = system.`mod`(a,b)
    if result < 0: result += b
proc `mod=`*[A,B](a :var A, b :B) = a = a mod b
proc `div=`*[A,B](a :var A, b :B) = a = a div b

proc `^`*[T](a :T, b :Int) :T =
    if b==0: 1
    else: doubling[T](a,b,proc(x,y:T):T = x*y)

proc fact[I]( n :I ) :I =
    var memo {.global.} = vect[I] [I(1)]
    if n.Int >= memo.len:
        for i in (memo.len,n.Int+1):
            memo.push memo[i-1] * i
    return memo[n.Int]

iterator divisor*(N :Int) :Int =
    var i = 1
    var s = vect[Int] []
    while i*i < N:
        if N mod i == 0:
            yield i
            s.push N div i
        i.inc
    if i*i == N: yield i
    for j in reverse(s.len):
        yield s[j]

proc divisor*( N :Int ) :Vect[Int] =
    result = @[]
    for d in N.divisor:
        result.add d


proc perm*[N,K]( n :N, k :K ) :N =
    fact(n) div fact(n-k)

proc comb*[I](n,k :I) :I =
    let k = min(k,n-k)
    result = 1
    for i in k.Int:
        result *= (n-i)
        result = result div (i+1)

proc eratos*( N :Int ) :Vect[Bool] =
    result = vect[Bool] N+1
    for i in (2,N+1): result[i] = true
    var i = 2
    while i * i <= N:
        if result[i]:
            var j = i * 2
            while j <= N:
                result[j] = false
                j += i
        i += 1

proc `ceilDiv`*( n: Int, m: Int ) :Int =
    return (n + m - 1) div m

proc gcd*(a, b :Int) :Int =
    if b == 0:
        return a
    return gcd(b, a mod b)
proc `gcd=`*(a :var Int, b :Int) =
    a = gcd(a,b)
proc gcd*(v :openarray[Int]) :Int =
    result = 0
    for n in v:
        result.gcd= n
proc lcm*(a, b :Int) :Int =
    return a div gcd(a, b) * b
proc `lcm=`*(a :var Int, b :Int) =
    a = lcm(a,b)
proc lcm*(v :openarray[Int]) :Int =
    result = 1
    for n in v:
        result.lcm= n

proc floorSum(n, m, a, b :Int) :Int =
    var (a,b) = (a,b)
    if a >= m:
        result += n * (n-1) div 2 * (a div m)
        a.mod= m
    if b >= m:
        result += n * (b div m)
        b.mod= m
    let t = a * n + b
    if t >= m:
        result += floorSum(t div m, a, m, t mod m)



##################
###   search   ###
##################
iterator repetition*[T](v :openarray[T],k :Int) :Vect[T] =
    var c = vect[Int](k)
    for _ in v.len^k:
        var r = vect[T] k
        for i in k: r[i] = v[c[i]]
        yield r
        for j in reverse(k):
            c[j].inc
            if c[j] == v.len: c[j] = 0
            else: break

iterator subSequence*[T](v :openarray[T]) :Vect[T] =
    for t in repetition([false,true],v.len):
        var r = vect[T] 0
        for i,b in t:
            if b: r.push v[i]
        yield r

iterator permutation*[T](v :openarray[T]) :Vect[T] =
    let n = v.len
    var c = vect[Int](n) do (i:Int) -> Int: n-i
    var t = vect[T] v
    yield t
    block outside:
        for _ in infty():
            block inside:
                for i in reverse(n):
                    c[i].dec
                    if c[i] != 0:
                        swap(t[i], t[n-c[i]])
                        yield t
                        break inside
                    var k = t[i]
                    for j in (i,n-1):
                        t[j]=t[j+1]
                    t[n-1] = k
                    c[i] = n-i
                break outside

iterator combination*[T](v :openarray[T],k :Int) :Vect[T] =
    var c = vect[Int] k
    var t, s = 0
    for _ in infty():
        for i in (t,v.len):
            c[s] = i
            s.inc
            if s == k:
                var r = vect[T] k
                for i in k: r[i] = v[c[i]]
                yield r
                break
        if s==0: break
        s.dec
        t = c[s] + 1


##################
###   modint   ###
##################
type ModInt = object
    data :Int
var MOD :Int = int.high
converter toModInt*(n :Int) :ModInt =
    result.data = n mod MOD
converter toInt*(n :ModInt) :Int =
    n.data
proc inverse*(n: ModInt) :ModInt =
    var (a,b,c,d) = (n.data, MOD, 1, 0)
    while b > 0:
        let t = a div b
        a -= t * b; (a,b) = (b,a)
        c -= t * d; (c,d) = (d,c)
    return c
proc `$`*(a :ModInt) :String = $a.data
proc `+`*(a, b :ModInt) :ModInt = (a.data + b.data) mod MOD
proc `-`*(a, b :ModInt) :ModInt = (a.data - b.data) mod MOD
proc `*`*(a, b :ModInt) :ModInt = (a.data * b.data) mod MOD
proc `/`*(a, b :ModInt) :ModInt = a * b.inverse
proc `==`*(a, b :ModInt) :Bool = a.data == b.data
proc `+=`*(a :var ModInt, b :ModInt) = a = a + b
proc `-=`*(a :var ModInt, b :ModInt) = a = a - b
proc `*=`*(a :var ModInt, b :ModInt) = a = a * b
proc `/=`*(a :var ModInt, b :ModInt) = a = a / b
proc `div`*(a, b :ModInt) :ModInt = a * b.inverse


#################
###   deque   ###
#################
type Deque[T] = object
    data :Vect[T]
    head, tail, count, mask :Int
proc deque[T](v :openarray[T]): Deque[T] =
    result = Deque[T](
        data: newSeq[T](4),
        head: 0, tail: 0, count: 0, mask: 3 )
    for x in v: result.pushRight x
proc len[T](d :Deque[T]) :Int = d.count
proc `[]`[T](d :Deque[T], i :Int) :T =
    d.data[(d.head + i) and d.mask]
proc peekLeft[T](d :Deque[T]) :T =
    d.data[d.head]
proc peekRight[T](d :Deque[T]) :T =
    d.data[(d.tail-1) and d.mask]
proc expand[T](d :var Deque[T]) =
    if d.data.len == d.count:
        let l = d.data.len
        d.data.setLen(l * 2)
        d.mask = d.mask * 2 + 1
        if d.head >= d.tail:
            for i in (d.head, l): d.data[i+l] = d.data[i]
            d.head += l
proc pushLeft[T](d :var Deque[T], x :T) =
    expand(d)
    d.count.inc
    d.head = (d.head-1) and d.mask
    d.data[d.head] = x
proc pushRight[T](d :var Deque[T], v :T) =
    expand(d)
    d.count.inc
    d.data[d.tail] = v
    d.tail = (d.tail+1) and d.mask
proc popLeft[T](d :var Deque[T]) :T =
    d.count.dec
    result = d.data[d.head]
    d.head = (d.head+1) and d.mask
proc popRight[T](d :var Deque[T]) :T  =
    d.count.dec
    d.tail = (d.tail-1) and d.mask
    result = d.data[d.tail]


#################
###   Stack   ###
#################
type Stack[T] = object
    data :Deque[T]
proc stack[T](v :openarray[T]) :Stack[T] =
    result.data = deque v
proc len*[T](s :Stack[T]) :Int = s.data.len
proc push*[T](s :var Stack[T], e :T) = s.data.pushRight(e)
proc front*[T](s :Stack[T]) :T = s.data.peekRight
proc pop*[T](s :var Stack[T]) :T = s.data.popRight


#################
###   Queue   ###
#################
type Queue[T] = object
    data :Deque[T]
proc queue[T](v :openarray[T]) :Queue[T] =
    result.data = deque v
proc len*[T](q :Queue[T]) :Int = q.data.len
proc push*[T](q :var Queue[T], e :T) = q.data.pushRight(e)
proc front*[T](q :Queue[T]) :T = q.data.peekLeft
proc pop*[T](q :var Queue[T]) :T = q.data.popLeft


###############
###   set   ###
###############
type AVL[T] = ref object
    mid :T
    l,r :AVL[T]
    dep :Int
proc depth[T](t :AVL[T]) :Int =
    if t == nil: 0 else: t.dep
proc len[T](t :AVL[T]) :Int =
    if t == nil: 0
    else: 1 + t.l.len + t.r.len
proc `shr`[T](t :var AVL[T]) =
    var s = AVL[T]()
    s.mid = t.mid; s.l = t.l.r; s.r = t.r;
    s.dep = max(s.l.depth,s.r.depth)+1
    t.mid = t.l.mid; t.r = s; t.l = t.l.l
    t.dep = max(t.l.depth,s.dep)+1
proc `shl`[T](t :var AVL[T]) =
    var s = AVL[T]()
    s.mid = t.mid; s.l = t.l; s.r = t.r.l
    s.dep = max(s.l.depth,s.r.depth)+1
    t.mid = t.r.mid; t.r = t.r.r; t.l = s
    t.dep = max(t.r.depth,s.dep)+1

type Set*[T] = object
    avl :AVL[T]
    `<` :(T,T) -> Bool
proc set*[T](v :openarray[T], `<`:proc(x,y:T):Bool =more) :Set[T] =
    result.`<` = `<`
    for x in v: result.push x
proc push*[T](s :var Set[T], x :T) =
    let `<` = s.`<`
    proc f(t :var AVL[T]) =
        if t == nil:
            t = AVL[T](); t.mid = x; t.dep = 1
        elif x < t.mid:
            t.l.f
            if t.l.dep > t.r.depth: t.shr
        elif t.mid < x:
            t.r.f
            if t.r.dep > t.l.depth: t.shl
    s.avl.f
proc `$`*[T](s :Set[T]) :String =
    proc f(t :AVL[T]) :String =
        if t == nil: ""
        else: "[" & f(t.l) & " " & $t.mid & " " & f(t.r) & "]"
    f(s.avl)
proc elem*[T](s :Set[T], x :T) :Bool =
    proc f(t :AVL[T]) :Bool =
        if t == nil: false
        elif s.`<`(x, t.mid): t.l.f
        elif s.`<`(t.mid, x): t.r.f
        else: true
    s.avl.f
iterator items*[T](s :Set[T]) :T =
    var a = stack [(s.avl,false)]
    var b = stack[T] []
    while a.len != 0:
        let (n,f) = a.pop
        if f: yield b.pop
        if n==nil: continue
        a.push (n.r,true)
        a.push (n.l,false)
        b.push n.mid
proc upperBound*[T](s :Set[T], x :T) :T =
    let `<` = s.`<`
    proc f(t :AVL[T]) :T =
        if t == nil: raise new IndexDefect
        if x < t.mid: return f(t.l)
        if t.mid < x:
            try: return f(t.r)
            except IndexDefect: return t.mid
        return t.mid
    s.avl.f
proc lowerBound*[T](s :Set[T], x :T) :T =
    let `<` = s.`<`
    proc f(t :AVL[T]) :T =
        if t == nil: raise new IndexDefect
        if t.mid < x: return f(t.r)
        if x < t.mid:
            try: return f(t.l)
            except IndexDefect: return t.mid
        return t.mid
    s.avl.f
proc max*[T](s :Set[T]) :T =
    proc f(t :AVL[T]) :T =
        if t.r == nil: t.mid
        else: t.r.f
    s.avl.f
proc min*[T](s :Set[T]) :T =
    proc f(t :AVL[T]) :T =
        if t.l == nil: t.mid
        else: t.l.f
    s.avl.f

################
###   sort   ###
################
proc `sort=`*[T](S :var Vect[T], compare :proc(x,y:T):Bool) =
    var stack = stack[ (Bool,Int,Int) ] [(true, 0, S.len)]
    while stack.len != 0:
        var (B, L, R) = stack.pop
        if R - L < 2: continue
        if B:
            stack.push( (false, L, R) )
            stack.push( (true, L, (L+R) div 2) )
            stack.push( (true, (L+R) div 2, R) )
            continue

        var temp = vect[T]( (L+R) div 2 - L )
        for i in temp.len: temp[i] = S[L+i]
        var (t, r) = (0, (L+R) div 2)
        for i in (L,R):
            if r == R or t != temp.len and compare(temp[t], S[r] ):
                S[i] = temp[t]
                t.inc
            else:
                S[i] = S[r]
                r.inc
proc `sort=`*[T](v :var Vect[T]) =
    v.sort= proc(x,y:T):Bool = x < y
proc sort*[T](v :openarray[T], comp :proc(x,y:T):Bool) :Vect[T] =
    result = vect[T] v
    result.sort= comp
proc sort*[T](v :openarray[T]) :Vect[T] =
    v.sort proc(x,y:T):Bool = x < y
proc sorted*[T](v :openarray[T], comp :proc(x,y:T):Bool) :Bool =
    for i in v.len - 1:
        if not comp(v[i],v[i+1]) and comp(v[i+1],v[i]):
            return false
    return true
proc sorted*[T](v :openarray[T]) :Bool =
    v.sorted proc(x,y:T):Bool = x < y

proc `max=`*[T]( x :var T; y :T ) =
    if x < y: x = y
proc `min=`*[T]( x :var T; y :T ) =
    if x > y: x = y
proc max[T](v :varargs[T]) :T =
    result = T.low
    for x in v: result.max = x
proc min[T](v :varargs[T]) :T =
    result = T.high
    for x in v: result.min = x
proc argMax*[T]( V :openArray[T] ) :Int =
    var max = T.low
    for i, e in V:
        if e > max:
            result = i
            max = e


################
###   read   ###
################
proc getchar*() :Char
    {.header:"stdio.h",importc:"getchar_unlocked".}
proc read*( T :typedesc ) :T =
    when T is Char:
        result = getchar()
        discard getchar()
    when T is String:
        result = ""
        while true:
            var c = getchar()
            if [' ', '\10', '\255'].elem c: break
            result.add c
    when T is Int:
        var
            sign = 1
            c = getchar()
        if c == '-':
            sign = -1
            c = getchar()
        while '0' <= c and c <= '9':
            result *= 10
            result += c.Int() - '0'.Int()
            c = getchar()
        result *= sign
    when T is tuple:
        for r in result.fields:
            r = r.type.read

proc read*( T :typedesc, N :Int ) :Vect[T] =
    result = vect[T] N
    for i in N:
        result[i] = T.read

proc read(T :typedesc, H,W :Int) :Tens[T] =
    result = Tens[T](H,W)
    for i in H:
        for j in W:
            result[i,j] = T.read

proc parseDigit(s:String) :Int =
    result = 0
    for c in s:
        result *= 10
        result += c.Int - '0'.Int



####################
###   disjoint   ###
####################
type Disjoint* = object
    data :Vect[Int]

proc disjoint*( n :Int ) :Disjoint =
    result.data = vect[Int] n
    for i in n: result.data[i] = -1

proc find*( d :var Disjoint, n :Int ) :Int =
    if d.data[n] < 0: return n
    d.data[n] = d.find( d.data[n] )
    return d.data[n]

proc union*( d :var Disjoint, n, m :Int ) =
    var n = d.find(n)
    var m = d.find(m)
    if n == m: return
    if d.data[m] < d.data[n]: swap( n, m )
    d.data[m] += d.data[n]
    d.data[n] = m

proc same*( d :var Disjoint, n, m :Int ) :Bool =
    d.find(n) == d.find(m)

proc size*( d :var Disjoint, n :Int ) :Int =
    - d.data[d.find(n)]



###################
###   segment   ###
###################
type Segment*[T] = object
    size :Int
    data :Vect[T]
    id :T
    op :proc(x,y:T):T

proc segment*[T](V:Vect[T], e:T, F:proc(x,y:T):T) :Segment[T] =
    result.id = e
    result.op = F
    result.size = 1
    while result.size < V.len: result.size *= 2
    result.data = vect[T](result.size * 2)
    for i in V.len: result.data[result.size + i] = V[i]
    for i in (V.len,result.size): result.data[result.size+i] = e
    for i in reverse(1,result.size):
        result.data[i] = F( result.data[2*i], result.data[2*i+1] )

proc `[]`[T](s :Segment[T], n :Int) :T = s.data[s.size+n]

proc `[]=`*[T]( S :var Segment[T], K :Int, X :T ) =
    var k = K + S.size
    S.data[k] = X
    while(k > 1):
        k = k div 2
        S.data[k] = S.op( S.data[k*2], S.data[2*k+1] )

proc `[]`*[T](s :Segment[T]; p :Slice[Int]) :T =
    var x,y = s.id
    var (l,r) = (p.a + s.size, p.b + s.size + 1)
    while l < r:
        if l mod 2 == 1:
            x = s.op(x, s.data[l])
            l.inc
        if r mod 2 == 1:
            r.dec
            y = s.op(s.data[r], y)
        l = l div 2
        r = r div 2
    return s.op(x,y)

#################
###   graph   ###
#################
type
    Node* = tuple[next:Int,weight:Int]
    Graph* = Vect[Vect[Node]]
proc readGraph*(n,m:Int,weight=false) :Graph =
    result = vect[Vect[(int,int)]] n
    for i in m:
        let a, b = Int.read - 1
        var w = 1
        if weight: w = Int.read
        result[a].push (b,w)
        result[b].push (a,w)
iterator edge*(g:Graph) :tuple[a,b,weight:Int] =
    for i in g.len:
        for j in g[i].len:
            yield (i,g[i][j].next,g[i][j].weight)
proc `$`*(g :Graph) :String =
    for i, a in g:
        for (b,c) in a:
            result &= "(" & $i & "->" & $b & " :" & $c & ") "
        result &= '\n'
proc dijkstra*(g :Graph, s :Int) :Vect[Int] =
    result = vect[Int](g.len, Int.high)
    var p = priority[(Int,Int)] proc(x,y:Node):bool =
        x.weight < y.weight
    p.push (s,0)
    while p.exist:
        let (i, c) = p.pop
        if result[i] < c: continue
        result[i] = c
        for (j, d) in g[i]:
            if c+d < result[j]:
                p.push (j,c+d)


##########################
####                  ####
####       main       ####
####                  ####
##########################
proc isPrime(n :Int) :Bool =
    var cnt = 0
    for i in divisor n:
        cnt += 1
    return cnt == 2

let S = Make:
    result = vect[Int] []
    var s = String.read
    for c in s: result.push c.Int - '0'.Int
var ans = 0
for v in [false,true].repetition S.len - 1:
    var a = vect[Int] [S[0]]
    for i in S.len - 1:
        if v[i]: a.push S[i+1]
        else: a[a.len-1] = a[a.len-1] * 10 + S[i+1]
    if a.sum.isPrime: ans += 1
echo ans