Harryxun/stf_run huggingface dataset:
from math import floor, ceil
h, w = map(int, input().split(' '))
result = []
if h%3 == 0 or w%3 == 0:
    print(0)
else:
    for i in range(1, h-1):
        x = i*w
        y = (h-i)*floor(w/2)
        z = (h-i)*ceil(w/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((h-i)/2)*w
        z = ceil((h-i)/2)*w
        result.append(max(x,y,z)-min(x,y,z))
    for i in range(1, w-1):
        x = i*h
        y = (w-i)*floor(h/2)
        z = (w-i)*ceil(h/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((w-i)/2)*h
        z = ceil((w-i)/2)*h
        result.append(max(x,y,z)-min(x,y,z))
    print(min(result))

### FIXED CODE ###

from math import floor, ceil
h, w = map(int, input().split(' '))
result = []
if h%3 == 0 or w%3 == 0:
    print(0)
elif h<3 or w<3:
    if h<3 and w>=3:
        for i in range(1, w-1):
            x = i*h
            y = (w-i)*floor(h/2)
            z = (w-i)*ceil(h/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((w-i)/2)*h
            z = ceil((w-i)/2)*h
            result.append(max(x,y,z)-min(x,y,z))
        print(min(result))
    elif h>=3 and w<3:
        for i in range(1, h-1):
            x = i*w
            y = (h-i)*floor(w/2)
            z = (h-i)*ceil(w/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((h-i)/2)*w
            z = ceil((h-i)/2)*w
            result.append(max(x,y,z)-min(x,y,z))
        print(min(result))
    else:
        print(1)
else:
    for i in range(1, h-1):
        x = i*w
        y = (h-i)*floor(w/2)
        z = (h-i)*ceil(w/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((h-i)/2)*w
        z = ceil((h-i)/2)*w
        result.append(max(x,y,z)-min(x,y,z))
    for i in range(1, w-1):
        x = i*h
        y = (w-i)*floor(h/2)
        z = (w-i)*ceil(h/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((w-i)/2)*h
        z = ceil((w-i)/2)*h
        result.append(max(x,y,z)-min(x,y,z))
    print(min(result))
n,k=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
for i in range(1,k+1):
    if n-k>=i-1:
        a=modcomb(k-1,i-1,INF)
        b=modcomb(n-k+1,i,INF)
        ans=(a*b)%INF
        print(ans)
    else:
        print(0)


### FIXED CODE ###

n,k=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
for i in range(1,k+1):
    if n-k>=i-1:
        if k-1==0 and i-1==0:
            a=1
        else:
            a=modcomb(k-1,i-1,INF)
        if n-k+1==0 and i==0:
            b=1
        else:
            b=modcomb(n-k+1,i,INF)
        ans=(a*b)%INF
        print(ans)
    else:
        print(0)
a,b,c,d,e,f = map(int, input().split())

w = [i+j for i in range(0,f+1,100*a) for j in range(0,f+1,100*b) if i+j <= f]
s = [i+j for i in range(0,f+1,c) for j in range(0,f+1,d) if i+j <= f]

W = f//(100*b)
S = 0
for ww in w :
    for ss in s :
        if ww+ss > f or ww == 0:
            continue
        elif ss/(ss+ww) > S/(W+S) and e >= 100*ss/ww:
            W = ww
            S = ss

print(W+S, S)

### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())

w = [i+j for i in range(0,f+1,100*a) for j in range(0,f+1,100*b) if i+j <= f]
s = [i+j for i in range(0,f+1,c) for j in range(0,f+1,d) if i+j <= f]

W = w[-1]
S = 0
for ww in w :
    for ss in s :
        if ww+ss > f or ww == 0:
            continue
        elif ss/(ss+ww) > S/(W+S) and e >= 100*ss/ww:
            W = ww
            S = ss

print(W+S, S)
import math
phi = (1 + math.sqrt(5)) / 2
def counter(n):
    if n == 1:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = round(phi**(a[0]) / math.sqrt(5)) % (10**9+7)
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)
print(ans)

### FIXED CODE ###

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 0
        for _ in range(n-1):
            (a, b) = (a+b, a)
        return a % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)
from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    if m == 0:
        return 1
    if m == 1 or n == 1 or n == 0:
        return n
    v = modpow(n, m // 2)
    v = v * v % MOD
    if m % 2 == 1:
        v = v * n % MOD
    return v


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    n, m, k = map(int, input())
    solve(n, m, k)

    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


if __name__ == '__main__':
    main()
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# def find_n(x, y):
#     moves = int((x+y)/3)
#     for n in range(moves+1):
#         if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
#             return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


def cmb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


def main():
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    x, y = map(int, input().split())

    if (x+y) % 3:
        print(0)
        sys.exit()

    # n, m = find_n(x, y)

    n = int(((x*2 - y) / 3)) % mod
    m = int(((y*2 - x) / 3)) % mod

    ans = cmb(n+m, min([n, m]))

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# def find_n(x, y):
#     moves = int((x+y)/3)
#     for n in range(moves+1):
#         if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
#             return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


def cmb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)

    return g1[n] * g2[r] * g2[n-r] % mod


def main():
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    x, y = map(int, input().split())

    if (x+y) % 3:
        print(0)
        sys.exit()

    # n, m = find_n(x, y)

    n = int(((x*2 - y) // 3))
    m = int(((y*2 - x) // 3))

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()
n = input()

lst = []
res = []

while n > 0:
    lst.append(n%10)
    n //= 10
lst.reverse()

for i in lst:
    if i == 1:
        res.append(9)
    elif i == 9:
        res.append(1)
    else:
        res.append(i)

S = ""

for j in res:
    Str += str(j)

print(S)


### FIXED CODE ###

n = int(input())

lst = []
res = []

while n > 0:
    lst.append(n%10)
    n //= 10
    
lst.reverse()


for i in lst:
    if i == 1:
        res.append(9)
    elif i == 9:
        res.append(1)
    else:
        res.append(i)


S = ""

for j in res:
    S += str(j)

print(S)
N = int(input())
v_list = input().split()
v_list = [int(v_list(i)) for i in range(N)]
v_list.sort()
ans = int(v_list[0])
for i in range(1, N):
    ans = (ans + int(v_list[i]))/2 
print(ans)

### FIXED CODE ###

N = int(input())
v_list = input().split()
v_list = [int(v_list[i]) for i in range(N)]
v_list.sort()
ans = int(v_list[0])
for i in range(1, N):
    ans = (ans + int(v_list[i]))/2 
print(ans)
S=input()
ans=0
for i in range(2**(len(S)-1)):
    tmp=S[0]
    for j in range(len(S)-1):
        if ((i >> j) & 1) == 1:
            x+="+"
        x+=S[j+1]
    ans+=eval(x)
print(ans)

### FIXED CODE ###

S=input()
ans=0
for i in range(2**(len(S)-1)):
    x = S[0]
    for j in range(len(S)-1):
        if ((i >> j) & 1) == 1:
            x+="+"
        x += S[j+1]
    ans += eval(x)
print(ans)
import collections

n = int(input())
v = list(map(int, input().split()))
odd = []
even = []
for i in range(0, n - 1, 2):
	odd.append(v[i])
	even.append(v[i + 1])

co = collections.Counter(odd)
ce = collections.Counter(even)

if len(co) >= 2 and len(ce) >= 2:
	if co.most_common()[0][1] == ce.most_common()[0][1]:
		if co.most_common()[1][1] > ce.most_common()[1][1]:
			oddval = co.most_common()[1][0]
			evenval = ce.most_common()[0][0]
		else:
			oddval = co.most_common()[0][0]
			evenval = ce.most_common()[1][0]
	else:
		oddval = co.most_common()[0][0]
		evenval = ce.most_common()[0][0]

if len(co) == 1 and len(ce) >= 2:
	if ce.most_common()[0][0] != odd[0]:
		oddval = odd[0]
		evenval = ce.most_common()[0][0]
	else:
		oddval = odd[0] + 1
		evenval = ce.most_common()[0][0]

if len(ce) >= 2 and len(ce) == 1:
	if co.most_common()[0][0] != even[0]:
		evenval = even[0]
		oddval = co.most_common()[0][0]
	else:
		evenval = even[0] + 1
		oddval = co.most_common()[0][0]

if len(co) == 1 and len(ce) == 1:
	if odd[0] != even[0]:
		oddval = odd[0]
		evenval = even[0]
	else:
		oddval = odd[0] + 1
		evenval = even[0]


count = 0
for i in range(0, n - 1, 2):
	count += abs(oddval - v[i]) + abs(evenval - v[i + 1])

print(count)

### FIXED CODE ###

import collections

n = int(input())
v = list(map(int, input().split()))
odd = []
even = []
for i in range(0, n - 1, 2):
	odd.append(v[i])
	even.append(v[i + 1])
N = n // 2
co = collections.Counter(odd)
ce = collections.Counter(even)
omost = co.most_common(2)
emost = ce.most_common(2)
if len(omost) == 1 and len(emost) == 1:
	if omost[0][0] != emost[0][0]:
		print(0)
	else:
		print(N)
elif len(omost) == 1:
	print(N - emost[0][1])
elif len(emost) == 1:
	print(N - omost[0][1])
else:
	if omost[0][0] != emost[0][0]:
		print(n - omost[0][1] - emost[0][1])
	else:
		print(min(n - omost[0][1] - emost[1][1], n - omost[1][1] - emost[0][1]))
S = int(input())
# S = "SASA"
arr = []
for s in S:
    arr.append(s)
if (arr[0] == arr[1]):
    if (arr[2] == arr[3]):
        ans = "Yes"
    else:
        ans = "No"
else:
    if (arr.count(arr[0]) == 2 and arr.count(arr[1]) == 2):
        ans = "Yes"
    else:
        ans = "No"

print(ans)



### FIXED CODE ###

S = input()
arr = []
for s in S:
    arr.append(s)
if (arr[0] == arr[1]):
    if (arr[0] != arr[2] and arr[2] == arr[3]):
        ans = "Yes"
    else:
        ans = "No"
else:
    if (arr.count(arr[0]) == 2 and arr.count(arr[1]) == 2):
        ans = "Yes"
    else:
        ans = "No"

print(ans)
N, M = map(int, input().split())

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1])
    max_dis = max(max_dis, dis[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append(fib[-1] + fib[-2])
  
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1]
  
  print(ans % MOD)

### FIXED CODE ###

N, M = map(int, input().split())

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  if M == 0:
    max_dis = N
    a.append(-1)
  else:
    max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append((fib[-1] + fib[-2]) % MOD)
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1] % MOD
  
  print(ans % MOD)
import sys
    sys.setrecursionlimit(5000)
     
    N,M,K = list(map(int,input().split(' ')))
     
    friend_list = [0]*(N+1)
    bad_list = [0]*(N+1)
    group = {}
     
    parent = [i for i in range(N+1)]
     
    def union(x,y):
        x = find(x)
        y = find(y)
        parent[x] = y
     
    def find(x):
        if parent[x] == x:
            return x
        else:
            parent[x]= find(parent[x])
            return parent[x]
     
     
     
    for i in range(M):
        A,B = list(map(int,input().split(' ')))
        friend_list[A]+=1
        friend_list[B]+=1
        
        union(A,B)
     
    for i in range(1,N+1):
        oya = find(i)
        parent[i] = oya
        #print(oya)
        if oya in group:
            group[oya] = group[oya]+1
        else:
            group[oya]=1
     
    for i in range(K):
        A,B = list(map(int,input().split(' ')))
        if find(A)==find(B):
            bad_list[A]+=1
            bad_list[B]+=1
        
        #union(A,B)
     
     
     
    #print(parent)
    #print('parent')
     
    #print('friend')
    #print(friend_list)
    #print('bad')
    #print(bad_list) 
    #print(group)
     
    kouho = [0]*N
     
    for i in range(1,N+1):
        oya = find(i)
        abc = group[oya]-friend_list[i]-bad_list[i]-1
        kouho[i-1] = abc
     
    for k in kouho:
        print(k,end=" ")
    print()
     
    #print(parent)

### FIXED CODE ###

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
n = int(input())
cnt  = [0 for i in range(10001)]

for x in range(1,105):
    for y in range(1, 105):
        for z in range(1, 105):
                ans = x**2 + y**2 + z**2 + x*y + y*z + z*x 
                if ans <= 10000:    
                    cnt[ans] +=1
for i in range(1, N+1):  
    print(cnt[i])

### 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])
def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus.append(num)
    else:
      minus.append(num)

  pn = len(plus)
  mn = len(minus)

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()


### FIXED CODE ###


def main():
  n, k = map(int, input().split())

  mod = 10 ** 9 + 7

  if n == k:
    ans = 1
    for num in input().split():
      ans = (ans * int(num)) % mod

    print(ans % mod)
    return

  plus = []
  minus = []
  for num in input().split():
    num = int(num)
    if num >= 0:
      plus.append(num)
    else:
      minus.append(num)

  pn = len(plus)
  mn = len(minus)

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if k == 1 or plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()
N = 10000
p = [1]*(N + 1)
for i in range(4, N + 1, 2): p[i] = 0
a = [2]
for i in range(3, N + 1, 2):
    if p[i] == 1:
        a.append(a[-1] + i)
        for j in range(3*i, N + 1, 2*i): p[j] = 0

while True:
    n = int(input())
    if n == 0: break
    print(a[n - 1])

### FIXED CODE ###

N = 104743
p = [1]*(N + 1)
for i in range(4, N + 1, 2): p[i] = 0
a = [2]
for i in range(3, N + 1, 2):
    if p[i] == 1:
        a.append(a[-1] + i)
        for j in range(3*i, N + 1, 2*i): p[j] = 0

while True:
    n = int(input())
    if n == 0: break
    print(a[n - 1])
a,b,c = input().split()
print(max(b+c-a, 0))


### FIXED CODE ###

a, b, c = map(int, input().split())
print(max(b+c-a, 0))
n, m = map(int, input().split())

if 2 * n >= m:
    print(min(n, m//2)
else:
    print((2 * n + m) // 4)

### FIXED CODE ###

n, m = map(int, input().split())

if 2 * n >= m:
    print(min(n, m//2))
else:
    print((2 * n + m) // 4)
a=map(int,raw_input().split())
a=list(set(a))
b=0
for i in a:
    t=True
    for I in range(2,int(i**0.5)+1):
        if i%I==0:
            t=False
    if t: 
        b+=1
print(b)

### FIXED CODE ###

a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
        i+=1
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))
a,b,n=map(int,input().split())
a1=int(a*n/b)-a*int(n/b)
print(a1)

### FIXED CODE ###

K=int(input())
A,B=map(int,input().split())
for i in range(A,B+1):
    if i%K==0:
        print("OK")
        exit()
print("NG")
a, b, c, k = input().split()

if a >= k:
    sum = k
elif a + b >= k:
    sum = k
else:
    sum = a - c
    
print(sum)

### FIXED CODE ###

a, b, c, k = input().split()

a = int(a)
b = int(b)
c = int(c)
k = int(k)

if a >= k:
    sum = k
elif a + b >= k:
    sum = a
else:
    sum = a - (k - a - b)
    
print(sum)
import itertools
import copy
n,m,x = map(int,input().split())
ans = [0 for i in range(m)]
books = []
answer = 1000000000000000000000
for i in range(n):
    books.append(list(map(int,input().split())))
for i in range(n):
    stock = list(list(itertools.combinations([num for num in range(n)], i+1)))
    for j in stock:
        cost = 0
        ans = [0 for i in range(m)]
        for k in j:
            for e,l in enumerate(books[k]):
                if e == 0:
                    cost += l
                else:
                    ans[e-1] += l
            if min(ans) >= x and cost < answer:
                answer = copy.deepcopy(cost)
if answer = 1000000000000000000000:
    print(-1)
else:
    print(answer)


### FIXED CODE ###

import itertools
import copy
n,m,x = map(int,input().split())
ans = [0 for i in range(m)]
books = []
answer = 1000000000000000000000
for i in range(n):
    books.append(list(map(int,input().split())))
for i in range(n):
    stock = list(list(itertools.combinations([num for num in range(n)], i+1)))
    for j in stock:
        cost = 0
        ans = [0 for i in range(m)]
        for k in j:
            for e,l in enumerate(books[k]):
                if e == 0:
                    cost += l
                else:
                    ans[e-1] += l
            if min(ans) >= x and cost < answer:
                answer = copy.deepcopy(cost)
if answer == 1000000000000000000000:
    print(-1)
else:
    print(answer)
N = int(input())
P = list(input().split())
cnt = 0
for n in range(1,N-1):
     if P[n-1] < P[n] and P[n] < P[n+1]:
        cnt += 1
    elif P[n-1] > P[n] and P[n] > P[n+1]:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
P = [int(i)for i in input().split()]
cnt = 0
for n in range(1,N-1):
    if (P[n-1] < P[n] < P[n+1] or P[n-1] > P[n] > P[n+1]):
        cnt+=1
print(cnt)