Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A, B = [], []
    for n in range(N):
        a, b = il()
        A.append(a)
        B.append(b)
    A.reverse()
    B.reverse()

    ret = 0
    for a, b in zip(A, B):
        if (a + ret) % b == 0: continue
        while (a + ret) % b != 0:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A, B = [], []
    for n in range(N):
        a, b = il()
        A.append(a)
        B.append(b)

    ret = 0
    for n in reversed(range(N)):
        if (A[n] + ret) % B[n] == 0: continue
        else:
            ret += B[n] - ((A[n] + ret) % B[n])
    print(ret)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []

cnt_sum = 0
for i in range(M):
    cnt = BC[i][0]
    for j in range(N):
        if cnt_sum <= N:
            L.append(BC[i][1])
            cnt_sum += 1
            cnt -= 1
        elif L[j] < BC[i][1]:
            L[j] = BC[i][1]
            cnt -= 1
        if cnt <= 0:
            break
L.sort(reverse=True)
A.sort()
ans = sum(A)
LL = len(L)
for k in range(N):
    if k <= LL-1 and L[k] > A[k]:
        ans += (L[k] - A[k])
    else:
        break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
dp = [0] * (N + 2)
dp[0] = 1
mod = 10**9 + 7
for i in range(N):
    if not i + 1 in data:
        dp[i + 1] += dp[i]
    if not i + 2 in data:
        dp[i + 2] += dp[i]
print(dp[N] % mod)


### FIXED CODE ###

N, M = map(int,input().split())
data = []
dp = ['.' for i in range(N + 1)]
dp[0] = 1
dp[1] = 1
for i in range(M):
    k = int(input())
    data.append(k)
    dp[k] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[N] % mod)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

K = INT()

if K%2 == 0 or K%5 == 0:
	print(-1)
	exit()

cnt = 1
tmp = 1
while K*tmp != int("7"*cnt):
	if K*tmp > int("7"*cnt):
		cnt += 1
	if K*tmp == int("7"*cnt):
		break
	tmp += 1

print(cnt)



### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

K = INT()

tmp = 7
ans = 1
p = 1
mo = tmp%K
checked = [0]*(K+1)
checked[mo] = 1
while mo != 0:
	mo += 7*pow(10, p, K)
	mo %= K
	p += 1
	if checked[mo]:
		print(-1)
		break
	checked[mo] = 1
else:
	print(p)
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n+1):
    ans = 0
    for j in range(1, int(math.sqrt(i))):
        for k in range(1, int(math.sqrt(i))):
            temp = i-(3*((j*j)+(k*k))/4)-((j*k)/2)
            if temp > 0:
                z = math.sqrt(temp)-((j+k)/2)
                if z-int(z) == 0 and z > 0:
                    ans += 1
    print(ans)


### FIXED CODE ###

import math

n = int(input())
ans_list = [0 for i in range(n+1)]

for i in range(1,101):
    for j in range(1, 101):
        for k in range(1, 101):
            temp = i*i + j*j + k*k + i*j + j*k + k*i
            if temp <= n:
                ans_list[temp] += 1

for i in range(1, n+1):
    print(ans_list[i])
### BUGGY CODE ###

import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

def main():
    s = input()
    k = int(input())
    l = []
    ls = len(s)
    clist = sorted(list(set(list(s))))
    for i in clist:
        x = []
        for j in range(ls):
            if i == s[j]:
                x.append(j)
        for j in range(len(x)):
            idx = x[j]
            l.append(s[idx])
            for t in range(idx+1,ls):
                l.append(l[-1]+s[t])
        if len(set(l)) >= k:
            l = list(set(l))
            print(sorted(l)[k-1])
            break
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    k = int(input())
    l = set()
    ls = len(s)
    clist = sorted(list(set(list(s))))
    ladd = l.add
    for i in clist:
        x = []
        for j in range(ls):
            if i == s[j]:
                x.append(j)
        ladd(i)
        for j in range(len(x)):
            idx = x[j]
            xxx = s[idx]
            c = 0
            for t in range(idx+1,ls):
                xxx = xxx +s[t]
                ladd(xxx)
                c += 1
                if c > k:
                    break
        if len(l) >= k:
            l = list(l)
            print(sorted(l)[k-1])
            break
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

k=int(input())
ans=1
s_1=7%k
s_2=10%k
m=0
j=0
if k%2==0 or k%5==0:
  print(-1)
elif k==1 or k==7:
  print(1)
elif k%7==0:
  l=9*k/7
  i=0
  while j==0:
    m=(m+s_1*(((s_2**i)%l-1)%l))%l
    if m==0:
      j==1
    else:
      i+=1
      ans+=1
  print(ans)
else:
  l=9*k
  i=0
  while j==0:
    m=(m+s_1*(((s_2**i)%l-1)%l))%l
    if m==0:
      j==1
    else:
      i+=1
      ans+=1
  print(ans)

### FIXED CODE ###

k=int(input())
m=0
for i in range(k):
  m=(m*10+7)%k
  if m==0:
    break
  elif i==k-1:
    print(-1)
    exit()
print(i + 1)
### BUGGY CODE ###

N = int(input())

e = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
while e:
    a,b = e.pop(0)
    if d[a]==0 and d[b]!=0:
        d[a] = str(c[k])
        k+=1
    elif d[a]!=0 and d[b]==0:
        d[b] = str(c[k])
        k+=1
    else:
        e.append((a,b))
print(ans)
print(' '.join(d))

### FIXED CODE ###

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

e = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append((1,b))
    e[b].append((1,a))

c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
d = dijkstra(e,N,0)
d = [(d[i],i) for i in range(N)]
d.sort()
d = [(d[i][0],d[i][1],c[-i-1]) for i in range(N)]
d.sort(key=lambda x:x[1])
ans = [str(d[i][2]) for i in range(N)]
print(' '.join(ans))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys


def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * (y_length + 1) for i in range(x_length + 1)]
    for i, ch_x in enumerate(x, 1):
        row = memo[i]
        pre_row = memo[i-1]
        for j, ch_y in enumerate(y, 1):
            if ch_x == ch_y:
                row[j] = pre_row[j-1] + 1
            else:
                row[j] = max(pre_row[j], row[j-1])
    return memo[-1][-1]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
    print(*result, sep="\n")


### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys


def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * (y_length + 1) for i in range(x_length + 1)]
    for i, ch_x in enumerate(x, 1):
        row = memo[i]
        pre_row = memo[i-1]
        for j, ch_y in enumerate(y, 1):
            if ch_x == ch_y:
                row[j] = pre_row[j-1] + 1
            elif pre_row[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = pre_row[j]
    return memo[-1][-1]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
    print(*result, sep="\n")
### BUGGY CODE ###

import heapq
import math

n, k = map(int, input().split())
A = list(map(int, input().split()))

H = []

for i in range(n):
    heapq.heappush(H, (-A[i], 1))

for i in range(k):
    long, num = heapq.heappop(H)
    heapq.heappush(H, (long*num/(num+1), num+1) )

print(math.ceil(-H[0][0]))

### FIXED CODE ###

import math

n, k = map(int, input().split())
A = list(map(int, input().split()))

l = 1
r = 10**9+1

while l < r:
    mid = (l+r)//2
    count = 0
    for i in range(n):
        if A[i] > mid:
            count += math.ceil(A[i]//mid)

    if count <= k:
        r = mid
    else:
        l = mid+1


print(l)
### BUGGY CODE ###

n = int(input())

#print(n)
a = list(map(int, input().split()))


ans = 1
for i in range(n):
    ans *= a[i]

if ans > 1000000000000000000:
    print(-1)
    exit(0)

print(ans)
exit(0)

### C++と同じく、実行は、Opt + Ctl + N

'''
# -*- coding: utf-8 -*-
# get a integer
a = int(input())
# get two integers separated with half-width break
b, c = map(int, input().split())
# get a string
s = input()
# output
print('{} {}'.format(a+b+c, s))
'''


### FIXED CODE ###

n = int(input())

#print(n)
a = list(map(int, input().split()))

if 0 in a:
    print(0)
    exit(0)


ans = 1
for i in range(n):
    ans *= a[i]
    #if a[i]==0:
    #    print(0)
    #    exit(0)

    if ans > 1000000000000000000:
        print(-1)
        exit(0)

print(ans)
exit(0)

### C++と同じく、実行は、Opt + Ctl + N

'''
# -*- coding: utf-8 -*-
# get a integer
a = int(input())
# get two integers separated with half-width break
b, c = map(int, input().split())
# get a string
s = input()
# output
print('{} {}'.format(a+b+c, s))
'''
### BUGGY CODE ###

import math
def main():

    N = int(input())
    A = list(map(int, input().split()))

    def isprime(a):
        if a == 1: return False
        for i in range(2, int(math.sqrt(a))+1):
            if a % i == 0: return False
        return True

    primes = []
    for v in range(1, max(A)+1):
        if isprime(v):  primes.append(v)

    d = dict()
    ispair = True
    isset = True
    for v in A:
        for p in primes:
            if v % p == 0:
                d[p] = d.get(p, 0) + 1
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"
    return "not coprime"

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    A = list(map(int, input().split()))

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in set(prime_factorize(v)):
            d[u] = d.get(u, 0) + 1
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import itertools
n=int(input())
lis=list(map(int, input().split())) 
out=0
for conb in itertools.combinations(lis, 3):
    l=list(conb)
    a=l[0]
    b=l[1]
    c=l[2]
    if a < b + c and b < c + a and c < a + b:
        out+=1
print(out)

### FIXED CODE ###

import bisect
n=int(input())
lis=list(map(int, input().split())) 
lis.sort()
out=0
for i in range(n):
    for j in range(1+i,n):
        out+=bisect.bisect_left(lis,lis[i]+lis[j])-j-1
print(out)
### BUGGY CODE ###


def main():
    S = input()

    modN = 13
    modAns = 10**9+7
    dp_table = [[0 for idx in range(modN)] for _ in range(len(S)+1)]
    dp_table[0][0] = 1

    for digit in range(len(S)):
        if S[digit] == '?':
            for mod in range(modN):
                for add_num in range(10):
                    next_mod = (10*mod + add_num) % 13
                    dp_table[digit+1][next_mod] += dp_table[digit][mod]
        else:
            val = int(S[digit])
            for mod in range(modN):
                next_mod = (10*mod + val) % 13
                dp_table[digit+1][next_mod] += dp_table[digit][mod]
        for idx in range(modN):
            dp_table[digit+1][idx] %= modAns

    print(dp_table[-1][5])


if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():
    S = input()

    modN = 13
    modAns = 10**9+7
    dp_table = [[0 for idx in range(modN)] for _ in range(len(S)+1)]
    dp_table[0][0] = 1

    for digit in range(len(S)):
        if S[digit] == '?':
            for mod in range(modN):
                for add_num in range(10):
                    next_mod = (10*mod + add_num) % 13
                    dp_table[digit+1][next_mod] += dp_table[digit][mod]
        else:
            val = int(S[digit])
            for mod in range(modN):
                next_mod = (10*mod + val) % 13
                dp_table[digit+1][next_mod] += dp_table[digit][mod]
        for idx in range(modN):
            dp_table[digit+1][idx] %= modAns

    print(dp_table[-1][5])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

num_limit = int(input())
for i in range(1,num_limit+1):
    xyz_count = 0
    j_limit = int(i ** 0.5)
    for j in range(1,j_limit+1):
        for k in range(1,j + 1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j > k:
                        if k > l:
                            xyz_count += 6
                        else:
                            xyz_count += 3
                    elif k > l:
                        xyz_count += 3
                    else:
                        xyz_count += 1
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


n = int(input())
a = list(map(int, input().split()))

c = [0] * (max(a) + 1)
for e in a:
    c[e] += 1

ans = n
for e in a:
    c[e] -= 1
    for fct in fact(e):
        if c[fct]:
            ans -= 1
            break

    c[e] += 1

print(ans)


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
for i in range(1,N+1):
  count=0
  k=i//5+1
  for x in range(k):
    if(x==0):
      continue
    if(x>=21):
      break
    for y in range(x,k):
      if(y==0):
        continue
      if(y>=21 or x+y>=30):
        break
      for z in range(y,k):
        if(z==0):
          continue
        if(z>=21 or y+z>=30 or z+x>=30):
          break
        if((x+y)**2+(y+z)**2+(z+x)**2)//2==i:
          #print(x,y,z)
          #print(i)
          if (x==y and y==z and z==x):
            count+=1
          elif (x!=y and y!=z and z!=x):
            count+=6
          else:
            count+=3
  print(count)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = i*i+j*j+k*k+i*j+j*k+k*i;
      if v<10050:
        ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        #k = (n-r*i-j*g)//b
        if r*i+j*g+abs(((n-r*i-j*g)//b)*b) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
### BUGGY CODE ###


X = int(input())

def gen_divisor(x):
    for i in range(x, 0, -1):
        if x % i == 0:
            yield i

def gen_candidates(divisor):
    a = -119
    while True:
        a = a + 1
        b = a - divisor
        tmp = a**5 - b**5
        if  tmp == X:
            yield (a, b)
        if a >= 120:
            break


for divisor in gen_divisor(X):
    for a, b in gen_candidates(divisor):
        print(a,b)
        break
    else:
        continue
    break

### FIXED CODE ###

X = int(input())

for a in range(-119,119):
    for b in range(-119,119):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break
### BUGGY CODE ###

s = input()
t = input()

alphabet = 'abcdefghijklmnopqrstuvwxyz'
cache = []

def search(origin, c, offset):
    offset = offset % len(origin)
    o = origin[offset:] + origin
    try:
        return o.index(c)
    except ValueError:
        return None

for i in range(len(s)):
    cache.append({c2: 0 for c2 in alphabet})
    for c2 in alphabet:
        offset2 = search(s, c2, i+1)
        if offset2 is None:
            cache[i][c2] = None
            continue
        cache[i][c2] = offset2 + 1

a = search(s, t[0], 0)
if a is None:
    print(-1)
    exit()

result = a
for i in range(1, len(t)):
    k = cache[result % len(s)][t[i]]
    if k is None:
        print(-1)
        exit()
    result += k

print(result+1)


### FIXED CODE ###

from bisect import bisect
s = input()
t = input()

alphabet = 'abcdefghijklmnopqrstuvwxyz'
char = {c: [] for c in alphabet}
for i, c in enumerate(s):
    char[c].append(i)

if len(char[t[0]]) == 0:
    print(-1)
    exit()

result = char[t[0]][0]

for c in t[1:]:
    if len(char[c]) == 0:
        print(-1)
        exit()
    idx = bisect(char[c], result % len(s))
    result = result - result % len(s)
    try:
        result += char[c][idx]
    except IndexError:
        result += len(s) + char[c][0]

print(result+1)