You are given an integer number $n$. The following algorithm is applied to it:

  if $n = 0$, then end algorithm;  find the smallest prime divisor $d$ of $n$;  subtract $d$ from $n$ and go to step $1$. 

Determine the number of subtrations the algorithm will make.


-----Input-----

The only line contains a single integer $n$ ($2 \le n \le 10^{10}$).


-----Output-----

Print a single integer — the number of subtractions the algorithm will make.


-----Examples-----
Input
5

Output
1

Input
4

Output
2



-----Note-----

In the first example $5$ is the smallest prime divisor, thus it gets subtracted right away to make a $0$.

In the second example $2$ is the smallest prime divisor at both steps.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Number theory

Implementation


Solutions:
n = int(input())
ans = 0
p = 2
while p * p <= n:
	if n % p == 0:
		print(1 + (n - p) // 2)
		exit()
	p += 1
print(1)


n = int(input())
sqrt = int(n ** (1 / 2)) + 1
for i in range(2, sqrt):
	if n % i == 0:
		print(1 + (n - i) // 2)
		exit()
print(1)


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	maxi = n
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			maxi = i
			break
	print(1 + (n - maxi) // 2)


from math import sqrt
from math import ceil
n = int(input())
s_n = int(ceil(sqrt(n)))
for x in range(2, n, +1):
	if n % x == 0:
		print(int(1 + (n - x) / 2))
		exit(0)
	if x > s_n:
		print(1)
		exit(0)
print(1)


n = int(input())
j = 0
while n != 0:
	f = 0
	i = 0
	for i in range(2, int(pow(n, 1 / 2)) + 1):
		if n % i == 0:
			f = 1
			j += 1
			n -= i
			break
	if i == 2 and f == 1:
		j += n // 2
		break
	if f == 0:
		j += 1
		break
print(j)


num = int(input())
n = int(num ** 0.5)
flag = False
i = 2
while i <= n:
	if num % i == 0:
		flag = True
		break
	i += 1
if not flag:
	print(1)
else:
	num = num - i
	print(num // 2 + 1)


def primefactors(n):
	i = 2
	blanck = []
	while i ** 2 <= n:
		if n % i == 0:
			blanck.append(i)
			while n % i == 0:
				n //= i
		else:
			i += 1
	if n > 1:
		blanck.append(n)
		n = 1
	return blanck

def brute(n):
	cnt = 0
	while n:
		x = primefactors(n)
		n -= x[0]
		cnt += 1
	return cnt

def f(n):
	cnt = 0
	t = primefactors(n)[0]
	if n % 2 != 0:
		n -= t
		cnt += 1
	return cnt + n // 2
n = int(input())
print(f(n))


def primerange(n):
	size = n // 2
	sieve = [1] * size
	limit = int(n ** 0.5)
	for i in range(1, limit):
		if sieve[i]:
			val = 2 * i + 1
			tmp = (size - 1 - i) // val
			sieve[i + val::val] = [0] * tmp
	return [2] + [i * 2 + 1 for (i, v) in enumerate(sieve) if v and i > 0]

def isprime(a, l):
	for i in l:
		if a % i == 0:
			return False
	return True
n = int(input())
prime = primerange(int(n ** 0.5) + 1)
if n % 2 == 0:
	print(n // 2)
elif isprime(n, prime):
	print(1)
else:
	for i in prime:
		if n % int(i) == 0:
			n -= int(i)
			break
	print(n // 2 + 1)


import math as mt
t = 1

def sp(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n
for _ in range(t):
	n = int(input())
	x = sp(n)
	if n % 2 == 0:
		print(n // 2)
	else:
		print((n - x) // 2 + 1)


from math import sqrt, ceil

def main():
	n = int(input())
	if not n % 2:
		print(n // 2)
		return
	stan = False
	for i in range(3, ceil(sqrt(n) + 1)):
		if not n % i:
			n -= i
			print(n // 2 + 1)
			return
	print(1)
	return
main()


def fact(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return i
	return n
n = int(input())
ans = 0
k = fact(n)
if k != 2:
	print((n - k) // 2 + 1)
else:
	print(n // k)


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	(x, b) = (int(math.sqrt(n)), 1)
	for i in range(3, x + 1, 2):
		if n % i == 0:
			b = i
			break
	if b == 1:
		b = n
	print((n - b) // 2 + 1)


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if a[i] == 1:
			j = i * 2
			while j < int(n ** 0.5) + 1:
				a[j] = 0
				j += i
n = int(input())
a = [1] * (int(n ** 0.5) + 1)
prime(n)

def findprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if a[i] == 1 and n % i == 0:
			return i
	return n
if n % 2 == 0:
	print(n // 2)
else:
	print(1 + (n - findprime(n)) // 2)


n = int(input())
k = 0
p = 1
for i in range(2, int(n ** 0.5 // 1) + 1):
	if n % i == 0:
		if i == 2:
			p = i
		if (i - 1) % 4 == 0 and p == 1:
			p = i
		elif (i + 1) % 4 == 0 and p == 1:
			p = i
		if i != n // i:
			k += 2
		else:
			k += 1
if k == 0:
	print(1)
else:
	print((n - p) // 2 + 1)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	d = 0
	for i in range(3, n, 2):
		if i * i > n:
			break
		if n % i == 0:
			d = i
			break
	if d == 0:
		d = n
	print(1 + (n - d) // 2)


n = int(input())

def prime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
if n & 1 == 0:
	print(n // 2)
elif prime(n):
	print(1)
else:
	ans = smallestDivisor(n)
	print(1 + (n - ans) // 2)


def min_divisor(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n

def main():
	n = int(input())
	if n % 2 != 0:
		n -= min_divisor(n)
		print(1 + n // 2)
	else:
		print(n // 2)
main()


import math
n = int(input())
for i in range(2, math.ceil(n ** 0.5) + 1):
	if n % i == 0:
		if i % 2 == 0:
			print(n // i)
			exit()
		else:
			print(1 + (n - i) // 2)
			exit()
print(1)


n = int(input())
arr = []
cnt = 0
if n % 2 == 1:
	cnt += 1
	f = 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			f = 1
			n -= i
			break
	if f == 0:
		n = 0
print(cnt + n // 2)


import sys
n = int(sys.stdin.readline().strip())

def find_min_prime(n):
	x = int(round(n ** 0.5 + 1))
	for i in range(2, x):
		if n % i == 0:
			return i
	return n
if n % 2 == 0:
	s = n // 2
else:
	d = find_min_prime(n)
	n = n - d
	s = 1 + n // 2
print(s)


is_prime = [0] * 1000100

def primes():
	for i in range(2, 1000010):
		if is_prime[i] == 0:
			is_prime[i] = 1
			for j in range(i * i, 1000010, i):
				is_prime[j] = -1
n = int(input())
primes()
if n % 2 == 0:
	print(n // 2)
else:
	primo = 0
	for i in range(3, int(n ** 0.5) + 2):
		if is_prime[i] == 1 and n % i == 0:
			primo = i
			break
	if primo == 0:
		n = 0
	print((n - primo) // 2 + 1)


import math

def divisors(n):
	divs = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			divs.extend([i, n // i])
	return set(divs)
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	divs = list(sorted(divisors(n)))
	if len(divs) == 0:
		print(1)
	else:
		for v in divs:
			tmpdivs = divisors(v)
			if len(tmpdivs) == 0:
				n -= v
				print(1 + n // 2)
				exit(0)
		print(1)


def mina(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n
n = int(input())
d = mina(n)
n = n - d
print(1 + n // 2)


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
import sys
import math
MAX = sys.maxsize
MAXN = 10 ** 6 + 10

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b, x, y):
	return abs(a - x) + abs(b - y)

def numIN():
	return map(int, sys.stdin.readline().strip().split())

def charIN():
	return sys.stdin.readline().strip().split()

def primeFactors(n):
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
n = int(input())
if isprime(n):
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	x = primeFactors(n)
	n -= x
	print(n // 2 + 1)


n = int(input())
count = 0

def IsPrime(n):
	d = 2
	while d * d <= n and n % d != 0:
		d += 1
	return d * d > n

def get_count(n, count):
	if n == 0:
		return count
	elif n % 2 == 0 and (not IsPrime(n)):
		return count + n // 2
	d = 0
	for i in range(2, n // 2 + 1):
		if IsPrime(i) and n % i == 0:
			d = i
			break
	else:
		d = n
	return get_count(n - d, count + 1)
if n % 2 == 0:
	print(n // 2)
elif IsPrime(n):
	print(1)
else:
	print(get_count(n, count))


from sys import *
n = int(input())
s = set()
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		s.add(i)
		s.add(n // i)
d = sorted(list(s))
ctr = 0
while n > 0:
	if n % 2:
		n -= d[1]
		ctr += 1
	else:
		ctr += n // 2
		n = 0
print(ctr)


def crives(n):
	p = 2
	while p * p <= n:
		if n % p == 0:
			return p
		p += 1
	return n
n = int(input())
cont = 0
if n % 2 != 0:
	n -= crives(n)
	cont += 1
resp = cont + int(n / 2)
print(resp)


from collections import Counter
import math

def printArr(arr):
	for i in arr:
		print(i, end=' ')

def proA(n):
	if n % 2 == 0:
		return n // 2
	i = 2
	k = 0
	while True:
		if i * i > n:
			break
		if n % i == 0:
			k = i
			break
		i += 1
	if k == 0:
		return 1
	return 1 + (n - k) // 2
n = int(input())
print(proA(n))


x = int(input())
for a in range(2, 10 ** 6):
	if x % a == 0:
		print(1 + (x - a) // 2)
		exit()
print(1)


n = int(input())
counter = 0
d = 0
for i in range(2, int(n ** 0.5 + 1)):
	if n % i == 0:
		counter = 1
		d = i
		break
if counter:
	print(1 + (n - d) // 2)
else:
	print(1)


import sys
import math
n = int(sys.stdin.readline())

def mpd(num):
	border = math.floor(num ** (1 / 2.0))
	c = 2
	is_found = False
	while c <= border and (not is_found):
		if num % c == 0:
			border2 = math.floor(c ** (1 / 2.0))
			is_not_found = False
			sc = 2
			while sc <= border2 and (not is_not_found):
				if c % sc == 0:
					is_not_found = True
				sc += 1
			if sc > border2:
				is_found = True
		if not is_found:
			c += 1
	if is_found:
		return c
	else:
		return num
n = n - mpd(n)
i = int(n / 2 + 1)
print(i)


import math
from collections import Counter, defaultdict
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	i = 2
	ans = 0
	while i * i <= n:
		if n % i == 0:
			ans += 1
			n -= i
			break
		i += 1
	if ans == 0:
		print(1)
	else:
		print(ans + n // 2)


def isprime(n):
	if n % 2 == 0:
		return 2
	else:
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				return i
		else:
			return n
n = int(input())
n = n - isprime(n)
print(n // 2 + 1)


n = int(input())
a = int(n ** 0.5) + 1
if n % 2 == 0:
	print(n // 2)
else:
	for i in range(3, a + 1, 2):
		if n % i == 0:
			print(1 + (n - i) // 2)
			exit()
	print('1')


import math
import sys
n = int(input())
for i in range(2, int(math.sqrt(n)) + 1):
	if n % i == 0:
		print(int((n - i) / 2 + 1))
		sys.exit()
print(1)


import math
arr = []

def primeFactors(n):
	while n % 2 == 0:
		arr.append(2)
		return
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			arr.append(i)
			n = n / i
	if n > 2:
		arr.append(n)
n = int(input())
primeFactors(n)
x = min(arr)
if n % 2 == 0:
	print(int(n / 2))
else:
	print(int((n - x) / 2) + 1)


import math

def find(n):
	if n == 2:
		return 2
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			return i
	return n
n = int(input())
ans = 0
fro = 2
while n > 0:
	if n % 2 == 0:
		ans += n // 2
		break
	f = find(n)
	ans += 1
	n -= f
print(ans)


import math

def smallestDividor(n):
	if n % 2 == 0:
		return 2
	for j in range(3, int(math.sqrt(n)) + 10, 2):
		if n % j == 0:
			return j
	return n
n = int(input())
compt = 0
while n != 0:
	d = smallestDividor(n)
	if d % 2 != 0:
		n = n - d
	else:
		break
	compt += 1
compt += n // 2
print(compt)


import sys
import math
n = int(input())
count = 0
primes = [2]
tmp = True
for i in range(2, int(math.sqrt(n)) + 1):
	if n % i == 0:
		tmp = False
		break
if tmp:
	print(1)
	sys.exit()
while n != 0:
	if n % 2 == 0:
		print(count + n // 2)
		sys.exit()
	temp = True
	for p in primes:
		if n % p == 0:
			count = count + 1
			n = n - p
			temp = False
			break
	if not temp:
		continue
	for i in range(primes[-1] + 1, 100000 + 1):
		tt = True
		for j in range(2, int(math.sqrt(i)) + 1):
			if i % j == 0:
				tt = False
				break
		if tt:
			primes.append(i)
			if n % i == 0:
				count = count + 1
				n = n - i
				break
print(count)


from os import path
import sys, time
from math import ceil, floor, gcd, log, log2, factorial
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, groupby, zip_longest, permutations
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
tup = lambda : map(int, sys.stdin.buffer.readline().split())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))
localsys = 0
start_time = time.time()
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def p(n):
	m = maxx
	while n % 2 == 0:
		n //= 2
		m = min(m, 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			m = min(m, i)
			n //= i
	if n > 1:
		m = min(m, n)
	return m
n = I()
m = p(n)
print(1 + (n - m) // 2)
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


n = int(input())
flag = 0
for i in range(2, int(n ** 0.5) + 1):
	if n % i == 0:
		print(1 + int((n - i) / 2))
		flag = 1
		break
if flag == 0:
	print(1)


s = input()
n = 0
for c in s:
	ch = ord(c) - ord('0')
	n = 10 * n + ch
i = 2
while i * i <= n:
	if n % i == 0:
		break
	i += 1
if n % i != 0:
	print(1)
elif i == 2:
	print(n // 2)
else:
	n -= i
	print(n // 2 + 1)


n = int(input())
least_prime_cache = {}
steps_cache = {}

def find_least_prime(end):
	for i in range(2, int(end ** 0.5 + 1)):
		if end % i == 0:
			return i
	return end

def find_steps(n):
	if n in steps_cache:
		return steps_cache[n]
	if not n % 2:
		return n // 2
	if n not in least_prime_cache:
		prime = find_least_prime(n)
		least_prime_cache[n] = prime
	prime = least_prime_cache[n]
	return 1 + find_steps(n - least_prime_cache[n])
print(find_steps(n))


import math

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

def sieve(n):
	ass = []
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	for i in range(n + 1):
		if is_prime[i]:
			ass.append(i)
	return ass
S = sieve(10 ** 5 + 50)
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	if is_prime(n):
		print(1)
		exit()
	for p in S:
		if n % p == 0:
			break
	print(1 + (n - p) // 2)


from math import sqrt

def get_first_divisor(n):
	s = set()
	for d in range(3, int(sqrt(n)) + 1, 2):
		if n % d == 0:
			return d
	return 1
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	p = get_first_divisor(n)
	if p == 1:
		print(1)
	else:
		print((n - p) // 2 + 1)


n = int(input())
result = 0
while n != 0:
	i = 2
	if n % i == 0:
		result += n // i
		break
	else:
		i = 3
		d = n
		while i * i <= n:
			if n % i == 0:
				d = i
				break
			i += 1
		n -= d
		result += 1
print(result)


num = int(input())
ans = 1
for i in range(2, int(num ** 0.5) + 1):
	if num % i == 0:
		ans = i
		break
if ans == 1:
	print(1)
elif ans == 2:
	print(num // 2)
else:
	print(1 + (num - ans) // 2)


from math import sqrt, floor

def isPrime(x):
	for i in range(2, floor(sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True

def divsub(n):
	if n == 0:
		return 0
	for i in range(2, floor(sqrt(n) + 1)):
		if n % i == 0 and isPrime(i):
			n = n - i
			return 1 + n // 2
	return 1

def main():
	n = int(input())
	print(divsub(n))
main()


import math

def isprime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	i = 3
	f = 0
	while i * i <= n:
		if n % i == 0:
			f = 1
			n -= i
			break
		i += 2
	if f == 0:
		n = 0
	print(1 + n // 2)


import math
n = int(input())
count = 0
while n % 2 != 0:
	flag = True
	for i in range(3, int(math.sqrt(n) + 1)):
		if n % i == 0:
			n -= i
			flag = False
			break
	if flag:
		n = 0
	count += 1
count += int(n / 2)
print(count)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 5)
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop

def solve(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return True
	return False
primes = []
for i in range(2, 10 ** 5 + 1):
	if not solve(i):
		primes.append(i)
n = int(input())
ans = 0
while n != 0:
	if n % 2 == 0:
		ans += n // 2
		break
	flag = 0
	for i in primes:
		if n % i == 0:
			n -= i
			ans += 1
			flag = 1
			break
	if not flag:
		if not solve(n):
			ans += 1
			break
print(ans)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	i = 3
	while i <= n // i:
		if n % i == 0:
			n -= i
			print(1 + n // 2)
			exit()
		i += 1
	print(1)


import configparser
import sys
input = sys.stdin.readline

def ceil_div(x, y):
	return -(-x // y)

def main():
	n = int(input())
	if n % 2 == 0:
		print(n // 2)
		return
	import math
	max_n = int(math.sqrt(n)) + 5
	prime = [True for i in range(max_n)]
	for i in range(2, max_n):
		if prime[i]:
			for j in range(i + i, max_n, i):
				prime[j] = False
	find = -1
	for i in range(3, max_n):
		if i * i > n:
			break
		if n % i == 0 and prime[i]:
			find = i
			break
	if find == -1:
		print(1)
	else:
		print(1 + (n - find) // 2)
main()


import math

def mysol(n):
	minDiv = 987654321
	off = 2
	ret = 0
	while n > 0:
		tgt = int(math.ceil(math.sqrt(n))) + 1
		while off < tgt:
			if n % off == 0:
				minDiv = off
				break
			off += 1
		if off == tgt:
			return 1
		n -= minDiv
		ret += 1
		divided = n // 2
		if n % 2 == 0:
			return ret + divided
		else:
			ret += divided
			n = divided
	return ret

def driver():
	n = int(input())
	print(mysol(n))
driver()


n = int(input())
if n % 2 == 0:
	divizor = 2
elif n % 2 == 0:
	divizor = 3
else:
	i = 2
	while 1:
		if n % i == 0:
			divizor = i
			break
		else:
			i += 1
			if i ** 2 > n:
				divizor = n
				break
n -= divizor
print(1 + n // 2)


import sys
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def solve(n):
	if n == 0:
		return 0
	i = 2
	ret = 0
	while i * i <= n:
		if n % i:
			i += 1
		else:
			if i == 2:
				return ret + n // i
			n -= i
			i = 2
			ret += 1
	if n > 1:
		return ret + 1
	return ret

def main():
	n = I()
	print(solve(n))
main()


import math
import bisect
import itertools
import sys
mod = 10 ** 9 + 7

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 == 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 binsearch(arr, b, low, high):
	if low == high:
		return low
	if arr[math.ceil((low + high) / 2)] < b:
		return binsearch(arr, b, low, math.ceil((low + high) / 2) - 1)
	else:
		return binsearch(arr, b, math.ceil((low + high) / 2), high)

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

def calc(n, m, r):
	s = 0
	for i in range(0, r + 1, 2):
		s += ncr1(n, i) * ncr1(m, i)
		s %= mod
	return s
n = int(input())
i = 2
if is_prime(n):
	exit(print(1))
while i <= int(n ** 0.5) + 1:
	if n % i == 0:
		break
	i += 1
n -= i
exit(print(n // 2 + 1))


import math
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
	quit()
for i in range(2, int(math.sqrt(n)) + 1):
	if n % i == 0:
		print(int((n - i) / 2) + 1)
		quit()
print(1)


def abc(n):
	for i in range(2, n):
		if i * i > n:
			break
		if n % i == 0:
			return i
	return n
n = int(input())
cnt = 0
if n % 2 != 0:
	n -= abc(n)
	cnt += 1
print(cnt + n // 2)


def d(n):
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
if n % 2 == 0:
	print(n // 2)
elif d(n) == n:
	print(1)
else:
	r = n - d(n)
	print(int(r / 2) + 1)


import math

def isdig(n):
	if n == 2:
		return 2
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			return i
	return n
n1 = int(input())
k = 0
while n1 > 0:
	if n1 % 2 == 0:
		k += n1 // 2
		break
	d = isdig(n1)
	k += 1
	n1 -= d
print(k)


v = int(input())
i = 2
while i * i <= v:
	if v % i == 0:
		print(1 + (v - i) // 2)
		exit(0)
	i += 1
print(1)


def smallest_prime(n):
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	n -= smallest_prime(n)
	print(1 + n // 2)


n = int(input())
count = 0
while n != 0:
	i = 2
	if n % 2 == 0:
		q = n // 2
		count += q
		n -= q * 2
	else:
		while i * i <= n:
			if n % i == 0:
				n -= i
				count += 1
				break
			i += 1
		else:
			count += 1
			n = 0
			break
print(count)


n = int(input())
i = 2
cnt = 0
ans = -1
while i * i <= n:
	if n % i == 0:
		ans = i
		break
	i += 1
if ans == -1:
	ans = n
n -= ans
print(n // 2 + 1)


import math

def is_prime_divisor(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	else:
		return True
n = int(input())
if is_prime_divisor(n):
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	for i in range(2, n + 1):
		if n % i == 0:
			print(int((n - i) // 2 + 1))
			break


n = int(input())
import math
limit = math.sqrt(n)
limit = math.ceil(limit)
limit = int(limit)
step = 0
while n > 0:
	prev = n
	for i in range(2, limit + 1):
		if n % i == 0:
			step += 1
			limit = i
			n = n - i
			break
	if n == prev:
		break
	if limit == 2:
		print(str(step + n // 2))
		exit()
if n > 0:
	print(1)
else:
	print(step)


import math

def smallest_div(x):
	for i in range(2, int(math.sqrt(x) + 1)):
		if x % i == 0:
			return i
	return x

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

def main():
	n = int(input())
	if prime(n):
		print(1)
	else:
		div = smallest_div(n)
		print(n // 2 - max(0, (div - 3) // 2))
main()


import math
n = int(input())
result = 0
flag = False
i = 2
while i < math.sqrt(n) + 1:
	if n % i == 0:
		flag = True
		n -= i
		result += 1
		break
	i += 1
if flag:
	result += n // 2
else:
	result = 1
print(result)


from math import sqrt
n = int(input())
r = sqrt(n)
d = 2
while d < r and n % d != 0:
	d += 1
if d > r:
	d = n
print(int(1 + (n - d) / 2))


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def f(n):
	l = []
	for i in range(2, n + 1):
		if n % i == 0:
			return i
n = int(input())
if isPrime(n):
	print(1)
else:
	(s, tp) = (0, 0)
	while True:
		k = n - tp
		n = n - tp
		if n % 2 == 0:
			s += n // 2
			break
		if k == 0:
			break
		else:
			tp = f(k)
			s += 1
	print(s)


from math import *
n = int(input())

def cp(m):
	for i in range(2, int(sqrt(m)) + 1):
		if m % i == 0:
			return False
	return True

def sp(m):
	for i in range(2, int(sqrt(m)) + 1):
		if m % i == 0 and cp(i):
			return i
	return 0

def lala(m):
	if m % 2 == 0:
		return int(m / 2)
	prm = cp(m)
	if prm:
		return 1
	spm = sp(m)
	return 1 + lala(m - spm)
print(lala(n))


n = int(input())
count = 0
rep = 2
while n != 0:
	if n % 2 == 0:
		count_temp = n / 2
		n -= 2 * count_temp
		count += count_temp
		continue
	while n % rep != 0 and rep * rep <= n:
		rep += 1
	if n % rep == 0:
		n -= rep
		count += 1
	else:
		n = 0
		count += 1
print(int(count))


n = int(input())
for i in range(2, min(100000, n)):
	if n % i == 0:
		if i == 2:
			print(n // 2)
		else:
			print((n - i) // 2 + 1)
		break
else:
	print(1)


n = int(input())

def primes_sieve(size):
	prime = [True] * (size + 1)
	prime[0] = prime[1] = False
	for i in range(2, size + 1):
		if prime[i]:
			for j in range(i * i, size + 1, i):
				prime[j] = False
	return [i for i in range(2, size + 1) if prime[i]]
primes = primes_sieve(int(n ** 0.5) + 10)

def minPrime(k):
	for p in primes:
		if k % p == 0:
			return p
	return k
ans = 0
if n & 1 == 1:
	n = n - minPrime(n)
	ans += 1
ans += n // 2
print(ans)


def prime_divisor(n):
	i = 2
	while i ** 2 <= n:
		if n % i == 0:
			return i
		i += 1
	return n
n = int(input())
sub = 0
if n % 2 != 0:
	n -= prime_divisor(n)
	sub += 1
print(int(sub + n / 2))


n = int(input())
t = 0
if n % 2 == 0:
	exit(print(n // 2))
for i in range(2, int(pow(n, 0.5)) + 1):
	if n % i == 0:
		t = 1
		break
if t != 1:
	exit(print('1'))
else:
	print(1 + (n - i) // 2)


import math

def sieve(x):
	if x % 2 == 0:
		return 2
	root = math.sqrt(x)
	root = int(root) + 1
	for i in range(3, root, 2):
		if x % i == 0:
			return i
	return 0
n = int(input())
ans = 0
while n > 0:
	div = sieve(n)
	if div == 0:
		ans += 1
		break
	elif div == 2:
		ans += n / div
		break
	ans += 1
	n -= div
print(int(ans))


import math

def helper(x):
	up = math.floor(math.sqrt(x))
	i = 2
	while i <= up:
		if x % i == 0:
			return i
		i += 1
	return x
n = int(input())
if n // 2 == 0:
	print(n // 2)
else:
	print(1 + (n - helper(n)) // 2)


def solve():
	n = int(input())
	if n % 2 == 0:
		print(n // 2)
		return
	for i in range(3, int(n ** 0.5) + 1):
		if n % i == 0:
			print((n - i) // 2 + 1)
			return
	print(1)
solve()


import math
n = int(input())

def f(n):
	x = 2
	while x * x <= n:
		if n % x == 0:
			return x
		x += 1
	return n
cnt = 0
while n % 2 != 0:
	n -= f(n)
	cnt += 1
print(int(cnt + n / 2))


import math

def menor_fator_primo(num):
	fatores = []
	if num % 2 == 0:
		return 2
	i = 3
	while i <= math.sqrt(num):
		if num % i == 0:
			return i
		i += 2
	return num
num = int(input())
cont = 0
while num > 0:
	if num % 2 == 0:
		cont += num // 2
		break
	else:
		cont += 1
		num -= menor_fator_primo(num)
print(cont)


def is_prime(n):
	if n == 2:
		return 0
	if not n & 1:
		return 2
	d = 3
	while d * d < n and n % d != 0:
		d += 2
	if n % d == 0:
		return d
	else:
		return 0
n = int(input())
dif = is_prime(n)
if dif == 0:
	print(1)
elif n & 1 == 1:
	print((n - dif) // 2 + 1)
else:
	print(n // 2)


b = True
n = int(input())
for i in range(2, int(n ** 0.5) + 1):
	if n % i == 0:
		b = False
		break
if b == True:
	print(1)
elif i == 2:
	print(n // 2)
else:
	print(1 + (n - i) // 2)


import math
n = int(input())
resposta = 0
if n % 2 == 0:
	resposta = n // 2
else:
	ok = False
	menor = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			menor = i
			ok = True
			break
	k = (n - menor) // 2
	if ok:
		resposta = k + 1
	else:
		resposta = 1
print(resposta)


n = int(input())
i = 2
z = 0
while i * i <= n:
	if n % i == 0:
		print(1 + (n - i) // 2)
		z += 1
		break
	i += 1
if z == 0:
	print(1)


n = int(input())
import math

def is_prime(n):
	count = 0
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			count += 1
	if count == 0:
		return True
	else:
		return False

def cf(n):
	if n % 2 == 0:
		print(int(n / 2))
	else:
		for i in range(2, int(math.sqrt(n) + 1)):
			if n % i == 0 and is_prime(i) == True:
				print(int((n - i) / 2 + 1))
				break
		if is_prime(n) == True:
			print('1')
cf(n)


n = int(input())
j = int(n ** 0.5 + 1)
q = n
for i in range(2, j):
	if n % i == 0:
		q = min(q, i)
		break
if q == n:
	print(1)
if q < n:
	print(1 + (n - q) // 2)


x = int(input())
i = 2
while i * i <= x:
	if x % i == 0:
		break
	else:
		i += 1
else:
	i = x
print(1 + (x - i) // 2)


n = int(input())
for d in range(2, 1 + int(n ** 0.5)):
	if not n % d:
		print((n - d + 2) // 2)
		break
else:
	print(1)


from math import sqrt as S

def isprime(n):
	for i in range(2, int(S(n)) + 1):
		if n % i == 0:
			return i
			break
	return n
n = int(input())
if isprime(n) == n:
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	k = isprime(n)
	print(1 + (n - k) // 2)


def subtraction(n):
	i = 2
	while i * i < n and n % i:
		i += 1
	if i * i > n:
		i = n
	return 1 + (n - i) // 2
n = int(input())
print(subtraction(n))


int_inp = lambda : int(input())
strng = lambda : input().strip()
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().split())
seq = lambda : list(map(int, input().split()))
import math
from collections import Counter, defaultdict
n = input()
n = int(n)
ans = 0
for i in range(2, 1000001):
	if n % i == 0:
		print(1 + (n - i) // 2)
		exit()
print(1)


import math

def no(x):
	k = int(math.sqrt(x))
	for i in range(3, k + 1, 2):
		if x % i == 0:
			return i
	return x
n = int(input())
if n & 1 == 0:
	print(int(n / 2))
else:
	m = n - no(n)
	print(int(1 + m / 2))


import math

def prime(a):
	for i in range(2, int(math.sqrt(a)) + 1):
		if a % i == 0:
			return 0
	return 1
n = int(input())
if prime(n) == 1:
	print('1')
elif n % 2 == 0:
	print(int(n / 2))
else:
	for i in range(2, n):
		if n % i == 0 and prime(i):
			d = i
			break
	print(1 + (n - d) // 2)


from math import sqrt
from math import floor

def deli(a):
	sq = sqrt(a)
	sq = floor(sq)
	if a % 2 == 0:
		return 2
	for i in range(3, sq + 1, 2):
		if a % i == 0:
			d = i
			return d
	return a
n = int(input())
c = 0
while n > 0:
	b = deli(n)
	if b == 2:
		c += n // 2
		break
	c += 1
	n -= b
print(c)


import math
numero = int(input())
aux = True
if numero % 2 == 0:
	print(int(numero / 2))
else:
	raiz = math.floor(math.sqrt(numero))
	for i in range(2, raiz + 1):
		if numero % i == 0:
			print(int((numero - i) / 2) + 1)
			aux = False
			break
	if aux:
		print(1)


import sys, math, io, os, time, itertools, collections
mod = 10 ** 9 + 7
sys.setrecursionlimit(10000)
i = sys.stdin.readline
p = sys.stdout.write
global start, end

def primefac(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	p = 3
	while p * p <= n:
		while n % p == 0:
			l.append(p)
			n = n // p
		p += 2
	if n > 2:
		l.append(n)
	return l[0]

def main():
	n = int(i())
	count = 0
	while n:
		if primefac(n) == 2:
			count += n // 2
			break
		n = n - primefac(n)
		count += 1
	p(str(count) + '\n')
t = 1
start = time.perf_counter()
for _ in range(t):
	main()
end = time.perf_counter()


n = int(input())
ans = 0
if n % 2 == 0:
	ans = n // 2
else:
	j = 3
	flag = 0
	while j * j <= n:
		if n % j == 0:
			n -= j
			flag = 1
			break
		j += 2
	if flag == 0:
		ans = 1
	else:
		ans = 1 + n // 2
print(ans)


def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors[0]
n = int(input())
if not n % 2:
	print(int(n / 2))
else:
	p = prime_factors(n)
	print(int(1 + (n - p) / 2))


import math

def leastprime(n):
	for num in range(2, int(math.sqrt(n)) + 1):
		if n % num == 0:
			return num

def solution(n):
	if n % 2 == 0:
		return int(n / 2)
	else:
		cnt = 0
		while n != 0:
			l = leastprime(n)
			if l:
				n = n - l
				cnt += int(n / 2)
				n = 0
			else:
				n = 0
			cnt += 1
		return int(cnt)
n = input()
n = int(n)
print(solution(n))


k = int(input())
i = 2
while i * i <= k:
	if k % i == 0:
		print(1 + (k - i) // 2)
		exit(0)
	i += 1
print(1)


from math import sqrt

def is_prime(n):
	if n == 1:
		return False
	if n == 2:
		return True
	for d in range(2, int(sqrt(n)) + 1):
		if n % d == 0:
			return False
	return True

def get_first_prime(n):
	for d in range(2, int(sqrt(n)) + 1):
		if n % d == 0 and is_prime(d):
			return d
	return n
n = int(input())
if is_prime(n):
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	n -= get_first_prime(n)
	print(1 + n // 2)


from math import sqrt
n = int(input())
limit = sqrt(n)
controller = 2
chain = 1
while controller < limit:
	if n % controller == 0:
		break
	controller += 1
if controller > limit:
	print(1)
else:
	n -= controller
	chain += n // 2
	print(chain)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	n = int(input())
	d = 2
	while d * d <= n:
		if n % d == 0:
			if d == 2:
				print(n // d)
			else:
				print((n - d) // 2 + 1)
			break
		d += 1
	else:
		print(1)
main()


from math import sqrt
n = int(input())
d = n
for i in range(2, int(sqrt(n)) + 1):
	if n % i == 0:
		d = i
		break
print(1 + (n - d) // 2)


import math

def smallest_prime(n):
	for i in range(3, int(math.sqrt(n)) + 1, 1):
		if not n % i:
			return i
	return n
n = int(input())
if not n % 2:
	print(int(n / 2))
else:
	a = smallest_prime(n)
	print(int((n - a) / 2 + 1))


import math
a = int(input())
if a % 2 == 0:
	print(a // 2)
else:
	for i in range(3, int(math.sqrt(a) + 1)):
		if a % i == 0:
			a -= i
			print(a // 2 + 1)
			exit(0)
	print(1)


from time import time
import os
import sys
from io import BytesIO, IOBase
from collections import *
from bisect import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def prog_name():
	n = int(input())
	cnt = 0
	while n > 0:
		if n % 2 == 0:
			cnt += n // 2
			n = 0
		else:
			a = 0
			i = 3
			while i * i <= n:
				if n % i == 0:
					a += 1
					n -= i
					break
				i += 2
			if a == 0:
				n -= n
			cnt += 1
	print(cnt)

def main():
	T = 1
	for unique in range(T):
		prog_name()
main()


import bisect
import math
n = int(input())
primelist = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059, 18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143, 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233, 18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423, 19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891, 19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071, 20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149, 20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261, 20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551, 20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693, 20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771, 20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897, 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983, 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067, 21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169, 21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491, 21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563, 21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647, 21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751, 21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943, 21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039, 22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123, 22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229, 22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543, 22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643, 22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727, 22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817, 22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943, 22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029, 23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099, 23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203, 23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447, 23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561, 23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007, 24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091, 24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169, 24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281, 24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413, 24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517, 24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659, 24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183, 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303, 25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391, 25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471, 25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603, 25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693, 25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799, 25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913, 25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999, 26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111, 26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203, 26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399, 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497, 26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711, 26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801, 26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987, 26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077, 27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211, 27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329, 27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691, 27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767, 27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051, 28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151, 28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283, 28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579, 28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649, 28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729, 28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837, 28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933, 28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167, 29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443, 29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573, 29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671, 29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819, 29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921, 29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059, 30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137, 30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241, 30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689, 30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803, 30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871, 30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983, 31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091, 31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183, 31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259, 31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357, 31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973, 31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059, 32063, 32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159, 32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257, 32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353, 32359, 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423, 32429, 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531, 32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587, 32603, 32609, 32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717, 32719, 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831, 32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933, 32939, 32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999, 33013, 33023, 33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091, 33107, 33113, 33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203, 33211, 33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343, 33347, 33349, 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427, 33457, 33461, 33469, 33479, 33487, 33493, 33503, 33521, 33529, 33533, 33547, 33563, 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613, 33617, 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703, 33713, 33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773, 33791, 33797, 33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871, 33889, 33893, 33911, 33923, 33931, 33937, 33941, 33961, 33967, 33997, 34019, 34031, 34033, 34039, 34057, 34061, 34123, 34127, 34129, 34141, 34147, 34157, 34159, 34171, 34183, 34211, 34213, 34217, 34231, 34253, 34259, 34261, 34267, 34273, 34283, 34297, 34301, 34303, 34313, 34319, 34327, 34337, 34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429, 34439, 34457, 34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537, 34543, 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649, 34651, 34667, 34673, 34679, 34687, 34693, 34703, 34721, 34729, 34739, 34747, 34757, 34759, 34763, 34781, 34807, 34819, 34841, 34843, 34847, 34849, 34871, 34877, 34883, 34897, 34913, 34919, 34939, 34949, 34961, 34963, 34981, 35023, 35027, 35051, 35053, 35059, 35069, 35081, 35083, 35089, 35099, 35107, 35111, 35117, 35129, 35141, 35149, 35153, 35159, 35171, 35201, 35221, 35227, 35251, 35257, 35267, 35279, 35281, 35291, 35311, 35317, 35323, 35327, 35339, 35353, 35363, 35381, 35393, 35401, 35407, 35419, 35423, 35437, 35447, 35449, 35461, 35491, 35507, 35509, 35521, 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593, 35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753, 35759, 35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863, 35869, 35879, 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969, 35977, 35983, 35993, 35999, 36007, 36011, 36013, 36017, 36037, 36061, 36067, 36073, 36083, 36097, 36107, 36109, 36131, 36137, 36151, 36161, 36187, 36191, 36209, 36217, 36229, 36241, 36251, 36263, 36269, 36277, 36293, 36299, 36307, 36313, 36319, 36341, 36343, 36353, 36373, 36383, 36389, 36433, 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497, 36523, 36527, 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587, 36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683, 36691, 36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767, 36779, 36781, 36787, 36791, 36793, 36809, 36821, 36833, 36847, 36857, 36871, 36877, 36887, 36899, 36901, 36913, 36919, 36923, 36929, 36931, 36943, 36947, 36973, 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057, 37061, 37087, 37097, 37117, 37123, 37139, 37159, 37171, 37181, 37189, 37199, 37201, 37217, 37223, 37243, 37253, 37273, 37277, 37307, 37309, 37313, 37321, 37337, 37339, 37357, 37361, 37363, 37369, 37379, 37397, 37409, 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501, 37507, 37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567, 37571, 37573, 37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649, 37657, 37663, 37691, 37693, 37699, 37717, 37747, 37781, 37783, 37799, 37811, 37813, 37831, 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907, 37951, 37957, 37963, 37967, 37987, 37991, 37993, 37997, 38011, 38039, 38047, 38053, 38069, 38083, 38113, 38119, 38149, 38153, 38167, 38177, 38183, 38189, 38197, 38201, 38219, 38231, 38237, 38239, 38261, 38273, 38281, 38287, 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371, 38377, 38393, 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543, 38557, 38561, 38567, 38569, 38593, 38603, 38609, 38611, 38629, 38639, 38651, 38653, 38669, 38671, 38677, 38693, 38699, 38707, 38711, 38713, 38723, 38729, 38737, 38747, 38749, 38767, 38783, 38791, 38803, 38821, 38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903, 38917, 38921, 38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023, 39041, 39043, 39047, 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133, 39139, 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217, 39227, 39229, 39233, 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323, 39341, 39343, 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419, 39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511, 39521, 39541, 39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659, 39667, 39671, 39679, 39703, 39709, 39719, 39727, 39733, 39749, 39761, 39769, 39779, 39791, 39799, 39821, 39827, 39829, 39839, 39841, 39847, 39857, 39863, 39869, 39877, 39883, 39887, 39901, 39929, 39937, 39953, 39971, 39979, 39983, 39989, 40009, 40013, 40031, 40037, 40039, 40063, 40087, 40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153, 40163, 40169, 40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283, 40289, 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433, 40459, 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529, 40531, 40543, 40559, 40577, 40583, 40591, 40597, 40609, 40627, 40637, 40639, 40693, 40697, 40699, 40709, 40739, 40751, 40759, 40763, 40771, 40787, 40801, 40813, 40819, 40823, 40829, 40841, 40847, 40849, 40853, 40867, 40879, 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961, 40973, 40993, 41011, 41017, 41023, 41039, 41047, 41051, 41057, 41077, 41081, 41113, 41117, 41131, 41141, 41143, 41149, 41161, 41177, 41179, 41183, 41189, 41201, 41203, 41213, 41221, 41227, 41231, 41233, 41243, 41257, 41263, 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381, 41387, 41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491, 41507, 41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603, 41609, 41611, 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669, 41681, 41687, 41719, 41729, 41737, 41759, 41761, 41771, 41777, 41801, 41809, 41813, 41843, 41849, 41851, 41863, 41879, 41887, 41893, 41897, 41903, 41911, 41927, 41941, 41947, 41953, 41957, 41959, 41969, 41981, 41983, 41999, 42013, 42017, 42019, 42023, 42043, 42061, 42071, 42073, 42083, 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187, 42193, 42197, 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283, 42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359, 42373, 42379, 42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443, 42451, 42457, 42461, 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533, 42557, 42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649, 42667, 42677, 42683, 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743, 42751, 42767, 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841, 42853, 42859, 42863, 42899, 42901, 42923, 42929, 42937, 42943, 42953, 42961, 42967, 42979, 42989, 43003, 43013, 43019, 43037, 43049, 43051, 43063, 43067, 43093, 43103, 43117, 43133, 43151, 43159, 43177, 43189, 43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291, 43313, 43319, 43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441, 43451, 43457, 43481, 43487, 43499, 43517, 43541, 43543, 43573, 43577, 43579, 43591, 43597, 43607, 43609, 43613, 43627, 43633, 43649, 43651, 43661, 43669, 43691, 43711, 43717, 43721, 43753, 43759, 43777, 43781, 43783, 43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933, 43943, 43951, 43961, 43963, 43969, 43973, 43987, 43991, 43997, 44017, 44021, 44027, 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101, 44111, 44119, 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201, 44203, 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273, 44279, 44281, 44293, 44351, 44357, 44371, 44381, 44383, 44389, 44417, 44449, 44453, 44483, 44491, 44497, 44501, 44507, 44519, 44531, 44533, 44537, 44543, 44549, 44563, 44579, 44587, 44617, 44621, 44623, 44633, 44641, 44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729, 44741, 44753, 44771, 44773, 44777, 44789, 44797, 44809, 44819, 44839, 44843, 44851, 44867, 44879, 44887, 44893, 44909, 44917, 44927, 44939, 44953, 44959, 44963, 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077, 45083, 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181, 45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289, 45293, 45307, 45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377, 45389, 45403, 45413, 45427, 45433, 45439, 45481, 45491, 45497, 45503, 45523, 45533, 45541, 45553, 45557, 45569, 45587, 45589, 45599, 45613, 45631, 45641, 45659, 45667, 45673, 45677, 45691, 45697, 45707, 45737, 45751, 45757, 45763, 45767, 45779, 45817, 45821, 45823, 45827, 45833, 45841, 45853, 45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959, 45971, 45979, 45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099, 46103, 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199, 46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307, 46309, 46327, 46337, 46349, 46351, 46381, 46399, 46411, 46439, 46441, 46447, 46451, 46457, 46471, 46477, 46489, 46499, 46507, 46511, 46523, 46549, 46559, 46567, 46573, 46589, 46591, 46601, 46619, 46633, 46639, 46643, 46649, 46663, 46679, 46681, 46687, 46691, 46703, 46723, 46727, 46747, 46751, 46757, 46769, 46771, 46807, 46811, 46817, 46819, 46829, 46831, 46853, 46861, 46867, 46877, 46889, 46901, 46919, 46933, 46957, 46993, 46997, 47017, 47041, 47051, 47057, 47059, 47087, 47093, 47111, 47119, 47123, 47129, 47137, 47143, 47147, 47149, 47161, 47189, 47207, 47221, 47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309, 47317, 47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419, 47431, 47441, 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527, 47533, 47543, 47563, 47569, 47581, 47591, 47599, 47609, 47623, 47629, 47639, 47653, 47657, 47659, 47681, 47699, 47701, 47711, 47713, 47717, 47737, 47741, 47743, 47777, 47779, 47791, 47797, 47807, 47809, 47819, 47837, 47843, 47857, 47869, 47881, 47903, 47911, 47917, 47933, 47939, 47947, 47951, 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049, 48073, 48079, 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179, 48187, 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281, 48299, 48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397, 48407, 48409, 48413, 48437, 48449, 48463, 48473, 48479, 48481, 48487, 48491, 48497, 48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589, 48593, 48611, 48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733, 48751, 48757, 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817, 48821, 48823, 48847, 48857, 48859, 48869, 48871, 48883, 48889, 48907, 48947, 48953, 48973, 48989, 48991, 49003, 49009, 49019, 49031, 49033, 49037, 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121, 49123, 49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201, 49207, 49211, 49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331, 49333, 49339, 49363, 49367, 49369, 49391, 49393, 49409, 49411, 49417, 49429, 49433, 49451, 49459, 49463, 49477, 49481, 49499, 49523, 49529, 49531, 49537, 49547, 49549, 49559, 49597, 49603, 49613, 49627, 49633, 49639, 49663, 49667, 49669, 49681, 49697, 49711, 49727, 49739, 49741, 49747, 49757, 49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831, 49843, 49853, 49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957, 49991, 49993, 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069, 50077, 50087, 50093, 50101, 50111, 50119, 50123, 50129, 50131, 50147, 50153, 50159, 50177, 50207, 50221, 50227, 50231, 50261, 50263, 50273, 50287, 50291, 50311, 50321, 50329, 50333, 50341, 50359, 50363, 50377, 50383, 50387, 50411, 50417, 50423, 50441, 50459, 50461, 50497, 50503, 50513, 50527, 50539, 50543, 50549, 50551, 50581, 50587, 50591, 50593, 50599, 50627, 50647, 50651, 50671, 50683, 50707, 50723, 50741, 50753, 50767, 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857, 50867, 50873, 50891, 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971, 50989, 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109, 51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199, 51203, 51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329, 51341, 51343, 51347, 51349, 51361, 51383, 51407, 51413, 51419, 51421, 51427, 51431, 51437, 51439, 51449, 51461, 51473, 51479, 51481, 51487, 51503, 51511, 51517, 51521, 51539, 51551, 51563, 51577, 51581, 51593, 51599, 51607, 51613, 51631, 51637, 51647, 51659, 51673, 51679, 51683, 51691, 51713, 51719, 51721, 51749, 51767, 51769, 51787, 51797, 51803, 51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899, 51907, 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009, 52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121, 52127, 52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201, 52223, 52237, 52249, 52253, 52259, 52267, 52289, 52291, 52301, 52313, 52321, 52361, 52363, 52369, 52379, 52387, 52391, 52433, 52453, 52457, 52489, 52501, 52511, 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571, 52579, 52583, 52609, 52627, 52631, 52639, 52667, 52673, 52691, 52697, 52709, 52711, 52721, 52727, 52733, 52747, 52757, 52769, 52783, 52807, 52813, 52817, 52837, 52859, 52861, 52879, 52883, 52889, 52901, 52903, 52919, 52937, 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003, 53017, 53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101, 53113, 53117, 53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201, 53231, 53233, 53239, 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327, 53353, 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437, 53441, 53453, 53479, 53503, 53507, 53527, 53549, 53551, 53569, 53591, 53593, 53597, 53609, 53611, 53617, 53623, 53629, 53633, 53639, 53653, 53657, 53681, 53693, 53699, 53717, 53719, 53731, 53759, 53773, 53777, 53783, 53791, 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891, 53897, 53899, 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993, 54001, 54011, 54013, 54037, 54049, 54059, 54083, 54091, 54101, 54121, 54133, 54139, 54151, 54163, 54167, 54181, 54193, 54217, 54251, 54269, 54277, 54287, 54293, 54311, 54319, 54323, 54331, 54347, 54361, 54367, 54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421, 54437, 54443, 54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541, 54547, 54559, 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629, 54631, 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727, 54751, 54767, 54773, 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877, 54881, 54907, 54917, 54919, 54941, 54949, 54959, 54973, 54979, 54983, 55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073, 55079, 55103, 55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213, 55217, 55219, 55229, 55243, 55249, 55259, 55291, 55313, 55331, 55333, 55337, 55339, 55343, 55351, 55373, 55381, 55399, 55411, 55439, 55441, 55457, 55469, 55487, 55501, 55511, 55529, 55541, 55547, 55579, 55589, 55603, 55609, 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667, 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763, 55787, 55793, 55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849, 55871, 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949, 55967, 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093, 56099, 56101, 56113, 56123, 56131, 56149, 56167, 56171, 56179, 56197, 56207, 56209, 56237, 56239, 56249, 56263, 56267, 56269, 56299, 56311, 56333, 56359, 56369, 56377, 56383, 56393, 56401, 56417, 56431, 56437, 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501, 56503, 56509, 56519, 56527, 56531, 56533, 56543, 56569, 56591, 56597, 56599, 56611, 56629, 56633, 56659, 56663, 56671, 56681, 56687, 56701, 56711, 56713, 56731, 56737, 56747, 56767, 56773, 56779, 56783, 56807, 56809, 56813, 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909, 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983, 56989, 56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097, 57107, 57119, 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193, 57203, 57221, 57223, 57241, 57251, 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331, 57347, 57349, 57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467, 57487, 57493, 57503, 57527, 57529, 57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641, 57649, 57653, 57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737, 57751, 57773, 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839, 57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943, 57947, 57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049, 58057, 58061, 58067, 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153, 58169, 58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229, 58231, 58237, 58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379, 58391, 58393, 58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481, 58511, 58537, 58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613, 58631, 58657, 58661, 58679, 58687, 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763, 58771, 58787, 58789, 58831, 58889, 58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943, 58963, 58967, 58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053, 59063, 59069, 59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141, 59149, 59159, 59167, 59183, 59197, 59207, 59209, 59219, 59221, 59233, 59239, 59243, 59263, 59273, 59281, 59333, 59341, 59351, 59357, 59359, 59369, 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441, 59443, 59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513, 59539, 59557, 59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659, 59663, 59669, 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747, 59753, 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879, 59887, 59921, 59929, 59951, 59957, 59971, 59981, 59999, 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091, 60101, 60103, 60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217, 60223, 60251, 60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353, 60373, 60383, 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497, 60509, 60521, 60527, 60539, 60589, 60601, 60607, 60611, 60617, 60623, 60631, 60637, 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719, 60727, 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811, 60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913, 60917, 60919, 60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043, 61051, 61057, 61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169, 61211, 61223, 61231, 61253, 61261, 61283, 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363, 61379, 61381, 61403, 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487, 61493, 61507, 61511, 61519, 61543, 61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613, 61627, 61631, 61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717, 61723, 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861, 61871, 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979, 61981, 61987, 61991, 62003, 62011, 62017, 62039, 62047, 62053, 62057, 62071, 62081, 62099, 62119, 62129, 62131, 62137, 62141, 62143, 62171, 62189, 62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297, 62299, 62303, 62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459, 62467, 62473, 62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549, 62563, 62581, 62591, 62597, 62603, 62617, 62627, 62633, 62639, 62653, 62659, 62683, 62687, 62701, 62723, 62731, 62743, 62753, 62761, 62773, 62791, 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897, 62903, 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987, 62989, 63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127, 63131, 63149, 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281, 63299, 63311, 63313, 63317, 63331, 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391, 63397, 63409, 63419, 63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493, 63499, 63521, 63527, 63533, 63541, 63559, 63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617, 63629, 63647, 63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719, 63727, 63737, 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809, 63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913, 63929, 63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037, 64063, 64067, 64081, 64091, 64109, 64123, 64151, 64153, 64157, 64171, 64187, 64189, 64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301, 64303, 64319, 64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453, 64483, 64489, 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613, 64621, 64627, 64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747, 64763, 64781, 64783, 64793, 64811, 64817, 64849, 64853, 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927, 64937, 64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033, 65053, 65063, 65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147, 65167, 65171, 65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267, 65269, 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419, 65423, 65437, 65447, 65449, 65479, 65497, 65519, 65521, 65537, 65539, 65543, 65551, 65557, 65563, 65579, 65581, 65587, 65599, 65609, 65617, 65629, 65633, 65647, 65651, 65657, 65677, 65687, 65699, 65701, 65707, 65713, 65717, 65719, 65729, 65731, 65761, 65777, 65789, 65809, 65827, 65831, 65837, 65839, 65843, 65851, 65867, 65881, 65899, 65921, 65927, 65929, 65951, 65957, 65963, 65981, 65983, 65993, 66029, 66037, 66041, 66047, 66067, 66071, 66083, 66089, 66103, 66107, 66109, 66137, 66161, 66169, 66173, 66179, 66191, 66221, 66239, 66271, 66293, 66301, 66337, 66343, 66347, 66359, 66361, 66373, 66377, 66383, 66403, 66413, 66431, 66449, 66457, 66463, 66467, 66491, 66499, 66509, 66523, 66529, 66533, 66541, 66553, 66569, 66571, 66587, 66593, 66601, 66617, 66629, 66643, 66653, 66683, 66697, 66701, 66713, 66721, 66733, 66739, 66749, 66751, 66763, 66791, 66797, 66809, 66821, 66841, 66851, 66853, 66863, 66877, 66883, 66889, 66919, 66923, 66931, 66943, 66947, 66949, 66959, 66973, 66977, 67003, 67021, 67033, 67043, 67049, 67057, 67061, 67073, 67079, 67103, 67121, 67129, 67139, 67141, 67153, 67157, 67169, 67181, 67187, 67189, 67211, 67213, 67217, 67219, 67231, 67247, 67261, 67271, 67273, 67289, 67307, 67339, 67343, 67349, 67369, 67391, 67399, 67409, 67411, 67421, 67427, 67429, 67433, 67447, 67453, 67477, 67481, 67489, 67493, 67499, 67511, 67523, 67531, 67537, 67547, 67559, 67567, 67577, 67579, 67589, 67601, 67607, 67619, 67631, 67651, 67679, 67699, 67709, 67723, 67733, 67741, 67751, 67757, 67759, 67763, 67777, 67783, 67789, 67801, 67807, 67819, 67829, 67843, 67853, 67867, 67883, 67891, 67901, 67927, 67931, 67933, 67939, 67943, 67957, 67961, 67967, 67979, 67987, 67993, 68023, 68041, 68053, 68059, 68071, 68087, 68099, 68111, 68113, 68141, 68147, 68161, 68171, 68207, 68209, 68213, 68219, 68227, 68239, 68261, 68279, 68281, 68311, 68329, 68351, 68371, 68389, 68399, 68437, 68443, 68447, 68449, 68473, 68477, 68483, 68489, 68491, 68501, 68507, 68521, 68531, 68539, 68543, 68567, 68581, 68597, 68611, 68633, 68639, 68659, 68669, 68683, 68687, 68699, 68711, 68713, 68729, 68737, 68743, 68749, 68767, 68771, 68777, 68791, 68813, 68819, 68821, 68863, 68879, 68881, 68891, 68897, 68899, 68903, 68909, 68917, 68927, 68947, 68963, 68993, 69001, 69011, 69019, 69029, 69031, 69061, 69067, 69073, 69109, 69119, 69127, 69143, 69149, 69151, 69163, 69191, 69193, 69197, 69203, 69221, 69233, 69239, 69247, 69257, 69259, 69263, 69313, 69317, 69337, 69341, 69371, 69379, 69383, 69389, 69401, 69403, 69427, 69431, 69439, 69457, 69463, 69467, 69473, 69481, 69491, 69493, 69497, 69499, 69539, 69557, 69593, 69623, 69653, 69661, 69677, 69691, 69697, 69709, 69737, 69739, 69761, 69763, 69767, 69779, 69809, 69821, 69827, 69829, 69833, 69847, 69857, 69859, 69877, 69899, 69911, 69929, 69931, 69941, 69959, 69991, 69997, 70001, 70003, 70009, 70019, 70039, 70051, 70061, 70067, 70079, 70099, 70111, 70117, 70121, 70123, 70139, 70141, 70157, 70163, 70177, 70181, 70183, 70199, 70201, 70207, 70223, 70229, 70237, 70241, 70249, 70271, 70289, 70297, 70309, 70313, 70321, 70327, 70351, 70373, 70379, 70381, 70393, 70423, 70429, 70439, 70451, 70457, 70459, 70481, 70487, 70489, 70501, 70507, 70529, 70537, 70549, 70571, 70573, 70583, 70589, 70607, 70619, 70621, 70627, 70639, 70657, 70663, 70667, 70687, 70709, 70717, 70729, 70753, 70769, 70783, 70793, 70823, 70841, 70843, 70849, 70853, 70867, 70877, 70879, 70891, 70901, 70913, 70919, 70921, 70937, 70949, 70951, 70957, 70969, 70979, 70981, 70991, 70997, 70999, 71011, 71023, 71039, 71059, 71069, 71081, 71089, 71119, 71129, 71143, 71147, 71153, 71161, 71167, 71171, 71191, 71209, 71233, 71237, 71249, 71257, 71261, 71263, 71287, 71293, 71317, 71327, 71329, 71333, 71339, 71341, 71347, 71353, 71359, 71363, 71387, 71389, 71399, 71411, 71413, 71419, 71429, 71437, 71443, 71453, 71471, 71473, 71479, 71483, 71503, 71527, 71537, 71549, 71551, 71563, 71569, 71593, 71597, 71633, 71647, 71663, 71671, 71693, 71699, 71707, 71711, 71713, 71719, 71741, 71761, 71777, 71789, 71807, 71809, 71821, 71837, 71843, 71849, 71861, 71867, 71879, 71881, 71887, 71899, 71909, 71917, 71933, 71941, 71947, 71963, 71971, 71983, 71987, 71993, 71999, 72019, 72031, 72043, 72047, 72053, 72073, 72077, 72089, 72091, 72101, 72103, 72109, 72139, 72161, 72167, 72169, 72173, 72211, 72221, 72223, 72227, 72229, 72251, 72253, 72269, 72271, 72277, 72287, 72307, 72313, 72337, 72341, 72353, 72367, 72379, 72383, 72421, 72431, 72461, 72467, 72469, 72481, 72493, 72497, 72503, 72533, 72547, 72551, 72559, 72577, 72613, 72617, 72623, 72643, 72647, 72649, 72661, 72671, 72673, 72679, 72689, 72701, 72707, 72719, 72727, 72733, 72739, 72763, 72767, 72797, 72817, 72823, 72859, 72869, 72871, 72883, 72889, 72893, 72901, 72907, 72911, 72923, 72931, 72937, 72949, 72953, 72959, 72973, 72977, 72997, 73009, 73013, 73019, 73037, 73039, 73043, 73061, 73063, 73079, 73091, 73121, 73127, 73133, 73141, 73181, 73189, 73237, 73243, 73259, 73277, 73291, 73303, 73309, 73327, 73331, 73351, 73361, 73363, 73369, 73379, 73387, 73417, 73421, 73433, 73453, 73459, 73471, 73477, 73483, 73517, 73523, 73529, 73547, 73553, 73561, 73571, 73583, 73589, 73597, 73607, 73609, 73613, 73637, 73643, 73651, 73673, 73679, 73681, 73693, 73699, 73709, 73721, 73727, 73751, 73757, 73771, 73783, 73819, 73823, 73847, 73849, 73859, 73867, 73877, 73883, 73897, 73907, 73939, 73943, 73951, 73961, 73973, 73999, 74017, 74021, 74027, 74047, 74051, 74071, 74077, 74093, 74099, 74101, 74131, 74143, 74149, 74159, 74161, 74167, 74177, 74189, 74197, 74201, 74203, 74209, 74219, 74231, 74257, 74279, 74287, 74293, 74297, 74311, 74317, 74323, 74353, 74357, 74363, 74377, 74381, 74383, 74411, 74413, 74419, 74441, 74449, 74453, 74471, 74489, 74507, 74509, 74521, 74527, 74531, 74551, 74561, 74567, 74573, 74587, 74597, 74609, 74611, 74623, 74653, 74687, 74699, 74707, 74713, 74717, 74719, 74729, 74731, 74747, 74759, 74761, 74771, 74779, 74797, 74821, 74827, 74831, 74843, 74857, 74861, 74869, 74873, 74887, 74891, 74897, 74903, 74923, 74929, 74933, 74941, 74959, 75011, 75013, 75017, 75029, 75037, 75041, 75079, 75083, 75109, 75133, 75149, 75161, 75167, 75169, 75181, 75193, 75209, 75211, 75217, 75223, 75227, 75239, 75253, 75269, 75277, 75289, 75307, 75323, 75329, 75337, 75347, 75353, 75367, 75377, 75389, 75391, 75401, 75403, 75407, 75431, 75437, 75479, 75503, 75511, 75521, 75527, 75533, 75539, 75541, 75553, 75557, 75571, 75577, 75583, 75611, 75617, 75619, 75629, 75641, 75653, 75659, 75679, 75683, 75689, 75703, 75707, 75709, 75721, 75731, 75743, 75767, 75773, 75781, 75787, 75793, 75797, 75821, 75833, 75853, 75869, 75883, 75913, 75931, 75937, 75941, 75967, 75979, 75983, 75989, 75991, 75997, 76001, 76003, 76031, 76039, 76079, 76081, 76091, 76099, 76103, 76123, 76129, 76147, 76157, 76159, 76163, 76207, 76213, 76231, 76243, 76249, 76253, 76259, 76261, 76283, 76289, 76303, 76333, 76343, 76367, 76369, 76379, 76387, 76403, 76421, 76423, 76441, 76463, 76471, 76481, 76487, 76493, 76507, 76511, 76519, 76537, 76541, 76543, 76561, 76579, 76597, 76603, 76607, 76631, 76649, 76651, 76667, 76673, 76679, 76697, 76717, 76733, 76753, 76757, 76771, 76777, 76781, 76801, 76819, 76829, 76831, 76837, 76847, 76871, 76873, 76883, 76907, 76913, 76919, 76943, 76949, 76961, 76963, 76991, 77003, 77017, 77023, 77029, 77041, 77047, 77069, 77081, 77093, 77101, 77137, 77141, 77153, 77167, 77171, 77191, 77201, 77213, 77237, 77239, 77243, 77249, 77261, 77263, 77267, 77269, 77279, 77291, 77317, 77323, 77339, 77347, 77351, 77359, 77369, 77377, 77383, 77417, 77419, 77431, 77447, 77471, 77477, 77479, 77489, 77491, 77509, 77513, 77521, 77527, 77543, 77549, 77551, 77557, 77563, 77569, 77573, 77587, 77591, 77611, 77617, 77621, 77641, 77647, 77659, 77681, 77687, 77689, 77699, 77711, 77713, 77719, 77723, 77731, 77743, 77747, 77761, 77773, 77783, 77797, 77801, 77813, 77839, 77849, 77863, 77867, 77893, 77899, 77929, 77933, 77951, 77969, 77977, 77983, 77999, 78007, 78017, 78031, 78041, 78049, 78059, 78079, 78101, 78121, 78137, 78139, 78157, 78163, 78167, 78173, 78179, 78191, 78193, 78203, 78229, 78233, 78241, 78259, 78277, 78283, 78301, 78307, 78311, 78317, 78341, 78347, 78367, 78401, 78427, 78437, 78439, 78467, 78479, 78487, 78497, 78509, 78511, 78517, 78539, 78541, 78553, 78569, 78571, 78577, 78583, 78593, 78607, 78623, 78643, 78649, 78653, 78691, 78697, 78707, 78713, 78721, 78737, 78779, 78781, 78787, 78791, 78797, 78803, 78809, 78823, 78839, 78853, 78857, 78877, 78887, 78889, 78893, 78901, 78919, 78929, 78941, 78977, 78979, 78989, 79031, 79039, 79043, 79063, 79087, 79103, 79111, 79133, 79139, 79147, 79151, 79153, 79159, 79181, 79187, 79193, 79201, 79229, 79231, 79241, 79259, 79273, 79279, 79283, 79301, 79309, 79319, 79333, 79337, 79349, 79357, 79367, 79379, 79393, 79397, 79399, 79411, 79423, 79427, 79433, 79451, 79481, 79493, 79531, 79537, 79549, 79559, 79561, 79579, 79589, 79601, 79609, 79613, 79621, 79627, 79631, 79633, 79657, 79669, 79687, 79691, 79693, 79697, 79699, 79757, 79769, 79777, 79801, 79811, 79813, 79817, 79823, 79829, 79841, 79843, 79847, 79861, 79867, 79873, 79889, 79901, 79903, 79907, 79939, 79943, 79967, 79973, 79979, 79987, 79997, 79999, 80021, 80039, 80051, 80071, 80077, 80107, 80111, 80141, 80147, 80149, 80153, 80167, 80173, 80177, 80191, 80207, 80209, 80221, 80231, 80233, 80239, 80251, 80263, 80273, 80279, 80287, 80309, 80317, 80329, 80341, 80347, 80363, 80369, 80387, 80407, 80429, 80447, 80449, 80471, 80473, 80489, 80491, 80513, 80527, 80537, 80557, 80567, 80599, 80603, 80611, 80621, 80627, 80629, 80651, 80657, 80669, 80671, 80677, 80681, 80683, 80687, 80701, 80713, 80737, 80747, 80749, 80761, 80777, 80779, 80783, 80789, 80803, 80809, 80819, 80831, 80833, 80849, 80863, 80897, 80909, 80911, 80917, 80923, 80929, 80933, 80953, 80963, 80989, 81001, 81013, 81017, 81019, 81023, 81031, 81041, 81043, 81047, 81049, 81071, 81077, 81083, 81097, 81101, 81119, 81131, 81157, 81163, 81173, 81181, 81197, 81199, 81203, 81223, 81233, 81239, 81281, 81283, 81293, 81299, 81307, 81331, 81343, 81349, 81353, 81359, 81371, 81373, 81401, 81409, 81421, 81439, 81457, 81463, 81509, 81517, 81527, 81533, 81547, 81551, 81553, 81559, 81563, 81569, 81611, 81619, 81629, 81637, 81647, 81649, 81667, 81671, 81677, 81689, 81701, 81703, 81707, 81727, 81737, 81749, 81761, 81769, 81773, 81799, 81817, 81839, 81847, 81853, 81869, 81883, 81899, 81901, 81919, 81929, 81931, 81937, 81943, 81953, 81967, 81971, 81973, 82003, 82007, 82009, 82013, 82021, 82031, 82037, 82039, 82051, 82067, 82073, 82129, 82139, 82141, 82153, 82163, 82171, 82183, 82189, 82193, 82207, 82217, 82219, 82223, 82231, 82237, 82241, 82261, 82267, 82279, 82301, 82307, 82339, 82349, 82351, 82361, 82373, 82387, 82393, 82421, 82457, 82463, 82469, 82471, 82483, 82487, 82493, 82499, 82507, 82529, 82531, 82549, 82559, 82561, 82567, 82571, 82591, 82601, 82609, 82613, 82619, 82633, 82651, 82657, 82699, 82721, 82723, 82727, 82729, 82757, 82759, 82763, 82781, 82787, 82793, 82799, 82811, 82813, 82837, 82847, 82883, 82889, 82891, 82903, 82913, 82939, 82963, 82981, 82997, 83003, 83009, 83023, 83047, 83059, 83063, 83071, 83077, 83089, 83093, 83101, 83117, 83137, 83177, 83203, 83207, 83219, 83221, 83227, 83231, 83233, 83243, 83257, 83267, 83269, 83273, 83299, 83311, 83339, 83341, 83357, 83383, 83389, 83399, 83401, 83407, 83417, 83423, 83431, 83437, 83443, 83449, 83459, 83471, 83477, 83497, 83537, 83557, 83561, 83563, 83579, 83591, 83597, 83609, 83617, 83621, 83639, 83641, 83653, 83663, 83689, 83701, 83717, 83719, 83737, 83761, 83773, 83777, 83791, 83813, 83833, 83843, 83857, 83869, 83873, 83891, 83903, 83911, 83921, 83933, 83939, 83969, 83983, 83987, 84011, 84017, 84047, 84053, 84059, 84061, 84067, 84089, 84121, 84127, 84131, 84137, 84143, 84163, 84179, 84181, 84191, 84199, 84211, 84221, 84223, 84229, 84239, 84247, 84263, 84299, 84307, 84313, 84317, 84319, 84347, 84349, 84377, 84389, 84391, 84401, 84407, 84421, 84431, 84437, 84443, 84449, 84457, 84463, 84467, 84481, 84499, 84503, 84509, 84521, 84523, 84533, 84551, 84559, 84589, 84629, 84631, 84649, 84653, 84659, 84673, 84691, 84697, 84701, 84713, 84719, 84731, 84737, 84751, 84761, 84787, 84793, 84809, 84811, 84827, 84857, 84859, 84869, 84871, 84913, 84919, 84947, 84961, 84967, 84977, 84979, 84991, 85009, 85021, 85027, 85037, 85049, 85061, 85081, 85087, 85091, 85093, 85103, 85109, 85121, 85133, 85147, 85159, 85193, 85199, 85201, 85213, 85223, 85229, 85237, 85243, 85247, 85259, 85297, 85303, 85313, 85331, 85333, 85361, 85363, 85369, 85381, 85411, 85427, 85429, 85439, 85447, 85451, 85453, 85469, 85487, 85513, 85517, 85523, 85531, 85549, 85571, 85577, 85597, 85601, 85607, 85619, 85621, 85627, 85639, 85643, 85661, 85667, 85669, 85691, 85703, 85711, 85717, 85733, 85751, 85781, 85793, 85817, 85819, 85829, 85831, 85837, 85843, 85847, 85853, 85889, 85903, 85909, 85931, 85933, 85991, 85999, 86011, 86017, 86027, 86029, 86069, 86077, 86083, 86111, 86113, 86117, 86131, 86137, 86143, 86161, 86171, 86179, 86183, 86197, 86201, 86209, 86239, 86243, 86249, 86257, 86263, 86269, 86287, 86291, 86293, 86297, 86311, 86323, 86341, 86351, 86353, 86357, 86369, 86371, 86381, 86389, 86399, 86413, 86423, 86441, 86453, 86461, 86467, 86477, 86491, 86501, 86509, 86531, 86533, 86539, 86561, 86573, 86579, 86587, 86599, 86627, 86629, 86677, 86689, 86693, 86711, 86719, 86729, 86743, 86753, 86767, 86771, 86783, 86813, 86837, 86843, 86851, 86857, 86861, 86869, 86923, 86927, 86929, 86939, 86951, 86959, 86969, 86981, 86993, 87011, 87013, 87037, 87041, 87049, 87071, 87083, 87103, 87107, 87119, 87121, 87133, 87149, 87151, 87179, 87181, 87187, 87211, 87221, 87223, 87251, 87253, 87257, 87277, 87281, 87293, 87299, 87313, 87317, 87323, 87337, 87359, 87383, 87403, 87407, 87421, 87427, 87433, 87443, 87473, 87481, 87491, 87509, 87511, 87517, 87523, 87539, 87541, 87547, 87553, 87557, 87559, 87583, 87587, 87589, 87613, 87623, 87629, 87631, 87641, 87643, 87649, 87671, 87679, 87683, 87691, 87697, 87701, 87719, 87721, 87739, 87743, 87751, 87767, 87793, 87797, 87803, 87811, 87833, 87853, 87869, 87877, 87881, 87887, 87911, 87917, 87931, 87943, 87959, 87961, 87973, 87977, 87991, 88001, 88003, 88007, 88019, 88037, 88069, 88079, 88093, 88117, 88129, 88169, 88177, 88211, 88223, 88237, 88241, 88259, 88261, 88289, 88301, 88321, 88327, 88337, 88339, 88379, 88397, 88411, 88423, 88427, 88463, 88469, 88471, 88493, 88499, 88513, 88523, 88547, 88589, 88591, 88607, 88609, 88643, 88651, 88657, 88661, 88663, 88667, 88681, 88721, 88729, 88741, 88747, 88771, 88789, 88793, 88799, 88801, 88807, 88811, 88813, 88817, 88819, 88843, 88853, 88861, 88867, 88873, 88883, 88897, 88903, 88919, 88937, 88951, 88969, 88993, 88997, 89003, 89009, 89017, 89021, 89041, 89051, 89057, 89069, 89071, 89083, 89087, 89101, 89107, 89113, 89119, 89123, 89137, 89153, 89189, 89203, 89209, 89213, 89227, 89231, 89237, 89261, 89269, 89273, 89293, 89303, 89317, 89329, 89363, 89371, 89381, 89387, 89393, 89399, 89413, 89417, 89431, 89443, 89449, 89459, 89477, 89491, 89501, 89513, 89519, 89521, 89527, 89533, 89561, 89563, 89567, 89591, 89597, 89599, 89603, 89611, 89627, 89633, 89653, 89657, 89659, 89669, 89671, 89681, 89689, 89753, 89759, 89767, 89779, 89783, 89797, 89809, 89819, 89821, 89833, 89839, 89849, 89867, 89891, 89897, 89899, 89909, 89917, 89923, 89939, 89959, 89963, 89977, 89983, 89989, 90001, 90007, 90011, 90017, 90019, 90023, 90031, 90053, 90059, 90067, 90071, 90073, 90089, 90107, 90121, 90127, 90149, 90163, 90173, 90187, 90191, 90197, 90199, 90203, 90217, 90227, 90239, 90247, 90263, 90271, 90281, 90289, 90313, 90353, 90359, 90371, 90373, 90379, 90397, 90401, 90403, 90407, 90437, 90439, 90469, 90473, 90481, 90499, 90511, 90523, 90527, 90529, 90533, 90547, 90583, 90599, 90617, 90619, 90631, 90641, 90647, 90659, 90677, 90679, 90697, 90703, 90709, 90731, 90749, 90787, 90793, 90803, 90821, 90823, 90833, 90841, 90847, 90863, 90887, 90901, 90907, 90911, 90917, 90931, 90947, 90971, 90977, 90989, 90997, 91009, 91019, 91033, 91079, 91081, 91097, 91099, 91121, 91127, 91129, 91139, 91141, 91151, 91153, 91159, 91163, 91183, 91193, 91199, 91229, 91237, 91243, 91249, 91253, 91283, 91291, 91297, 91303, 91309, 91331, 91367, 91369, 91373, 91381, 91387, 91393, 91397, 91411, 91423, 91433, 91453, 91457, 91459, 91463, 91493, 91499, 91513, 91529, 91541, 91571, 91573, 91577, 91583, 91591, 91621, 91631, 91639, 91673, 91691, 91703, 91711, 91733, 91753, 91757, 91771, 91781, 91801, 91807, 91811, 91813, 91823, 91837, 91841, 91867, 91873, 91909, 91921, 91939, 91943, 91951, 91957, 91961, 91967, 91969, 91997, 92003, 92009, 92033, 92041, 92051, 92077, 92083, 92107, 92111, 92119, 92143, 92153, 92173, 92177, 92179, 92189, 92203, 92219, 92221, 92227, 92233, 92237, 92243, 92251, 92269, 92297, 92311, 92317, 92333, 92347, 92353, 92357, 92363, 92369, 92377, 92381, 92383, 92387, 92399, 92401, 92413, 92419, 92431, 92459, 92461, 92467, 92479, 92489, 92503, 92507, 92551, 92557, 92567, 92569, 92581, 92593, 92623, 92627, 92639, 92641, 92647, 92657, 92669, 92671, 92681, 92683, 92693, 92699, 92707, 92717, 92723, 92737, 92753, 92761, 92767, 92779, 92789, 92791, 92801, 92809, 92821, 92831, 92849, 92857, 92861, 92863, 92867, 92893, 92899, 92921, 92927, 92941, 92951, 92957, 92959, 92987, 92993, 93001, 93047, 93053, 93059, 93077, 93083, 93089, 93097, 93103, 93113, 93131, 93133, 93139, 93151, 93169, 93179, 93187, 93199, 93229, 93239, 93241, 93251, 93253, 93257, 93263, 93281, 93283, 93287, 93307, 93319, 93323, 93329, 93337, 93371, 93377, 93383, 93407, 93419, 93427, 93463, 93479, 93481, 93487, 93491, 93493, 93497, 93503, 93523, 93529, 93553, 93557, 93559, 93563, 93581, 93601, 93607, 93629, 93637, 93683, 93701, 93703, 93719, 93739, 93761, 93763, 93787, 93809, 93811, 93827, 93851, 93871, 93887, 93889, 93893, 93901, 93911, 93913, 93923, 93937, 93941, 93949, 93967, 93971, 93979, 93983, 93997, 94007, 94009, 94033, 94049, 94057, 94063, 94079, 94099, 94109, 94111, 94117, 94121, 94151, 94153, 94169, 94201, 94207, 94219, 94229, 94253, 94261, 94273, 94291, 94307, 94309, 94321, 94327, 94331, 94343, 94349, 94351, 94379, 94397, 94399, 94421, 94427, 94433, 94439, 94441, 94447, 94463, 94477, 94483, 94513, 94529, 94531, 94541, 94543, 94547, 94559, 94561, 94573, 94583, 94597, 94603, 94613, 94621, 94649, 94651, 94687, 94693, 94709, 94723, 94727, 94747, 94771, 94777, 94781, 94789, 94793, 94811, 94819, 94823, 94837, 94841, 94847, 94849, 94873, 94889, 94903, 94907, 94933, 94949, 94951, 94961, 94993, 94999, 95003, 95009, 95021, 95027, 95063, 95071, 95083, 95087, 95089, 95093, 95101, 95107, 95111, 95131, 95143, 95153, 95177, 95189, 95191, 95203, 95213, 95219, 95231, 95233, 95239, 95257, 95261, 95267, 95273, 95279, 95287, 95311, 95317, 95327, 95339, 95369, 95383, 95393, 95401, 95413, 95419, 95429, 95441, 95443, 95461, 95467, 95471, 95479, 95483, 95507, 95527, 95531, 95539, 95549, 95561, 95569, 95581, 95597, 95603, 95617, 95621, 95629, 95633, 95651, 95701, 95707, 95713, 95717, 95723, 95731, 95737, 95747, 95773, 95783, 95789, 95791, 95801, 95803, 95813, 95819, 95857, 95869, 95873, 95881, 95891, 95911, 95917, 95923, 95929, 95947, 95957, 95959, 95971, 95987, 95989, 96001, 96013, 96017, 96043, 96053, 96059, 96079, 96097, 96137, 96149, 96157, 96167, 96179, 96181, 96199, 96211, 96221, 96223, 96233, 96259, 96263, 96269, 96281, 96289, 96293, 96323, 96329, 96331, 96337, 96353, 96377, 96401, 96419, 96431, 96443, 96451, 96457, 96461, 96469, 96479, 96487, 96493, 96497, 96517, 96527, 96553, 96557, 96581, 96587, 96589, 96601, 96643, 96661, 96667, 96671, 96697, 96703, 96731, 96737, 96739, 96749, 96757, 96763, 96769, 96779, 96787, 96797, 96799, 96821, 96823, 96827, 96847, 96851, 96857, 96893, 96907, 96911, 96931, 96953, 96959, 96973, 96979, 96989, 96997, 97001, 97003, 97007, 97021, 97039, 97073, 97081, 97103, 97117, 97127, 97151, 97157, 97159, 97169, 97171, 97177, 97187, 97213, 97231, 97241, 97259, 97283, 97301, 97303, 97327, 97367, 97369, 97373, 97379, 97381, 97387, 97397, 97423, 97429, 97441, 97453, 97459, 97463, 97499, 97501, 97511, 97523, 97547, 97549, 97553, 97561, 97571, 97577, 97579, 97583, 97607, 97609, 97613, 97649, 97651, 97673, 97687, 97711, 97729, 97771, 97777, 97787, 97789, 97813, 97829, 97841, 97843, 97847, 97849, 97859, 97861, 97871, 97879, 97883, 97919, 97927, 97931, 97943, 97961, 97967, 97973, 97987, 98009, 98011, 98017, 98041, 98047, 98057, 98081, 98101, 98123, 98129, 98143, 98179, 98207, 98213, 98221, 98227, 98251, 98257, 98269, 98297, 98299, 98317, 98321, 98323, 98327, 98347, 98369, 98377, 98387, 98389, 98407, 98411, 98419, 98429, 98443, 98453, 98459, 98467, 98473, 98479, 98491, 98507, 98519, 98533, 98543, 98561, 98563, 98573, 98597, 98621, 98627, 98639, 98641, 98663, 98669, 98689, 98711, 98713, 98717, 98729, 98731, 98737, 98773, 98779, 98801, 98807, 98809, 98837, 98849, 98867, 98869, 98873, 98887, 98893, 98897, 98899, 98909, 98911, 98927, 98929, 98939, 98947, 98953, 98963, 98981, 98993, 98999, 99013, 99017, 99023, 99041, 99053, 99079, 99083, 99089, 99103, 99109, 99119, 99131, 99133, 99137, 99139, 99149, 99173, 99181, 99191, 99223, 99233, 99241, 99251, 99257, 99259, 99277, 99289, 99317, 99347, 99349, 99367, 99371, 99377, 99391, 99397, 99401, 99409, 99431, 99439, 99469, 99487, 99497, 99523, 99527, 99529, 99551, 99559, 99563, 99571, 99577, 99581, 99607, 99611, 99623, 99643, 99661, 99667, 99679, 99689, 99707, 99709, 99713, 99719, 99721, 99733, 99761, 99767, 99787, 99793, 99809, 99817, 99823, 99829, 99833, 99839, 99859, 99871, 99877, 99881, 99901, 99907, 99923, 99929, 99961, 99971, 99989, 99991, 100003]
t = bisect.bisect(primelist, int(math.sqrt(n)))
if n % 2 == 0:
	print(n // 2)
	exit()
else:
	t = bisect.bisect(primelist, int(math.sqrt(n)))
	for i in range(t + 1):
		if n % primelist[i] == 0:
			print((n - primelist[i]) // 2 + 1)
			exit()
print(1)


import sys
import math
sys.setrecursionlimit(100000000)
lines = []
for line in sys.stdin:
	lines.append(line.rstrip('\n'))
aNumber = int(lines.pop(0))

def decompose(n):
	i = 2
	result = []
	while n > 1:
		while n % i == 0:
			result.append(i)
			n = n / i
		i = i + 1
	return result

def minimumDivisor(n):
	i = 2
	objective = math.floor(math.sqrt(n)) + 1
	while n > 1:
		if i >= objective:
			return n
		while n % i == 0:
			return i
			n = n / i
		i = i + 1
	return n

def answer(n):
	if n == 0:
		return 0
	if n % 2 == 0:
		return int(n / 2)
	return 1 + answer(n - minimumDivisor(n))
print(answer(aNumber))


n = int(input())
import math
pr = []
if n % 2 == 0:
	print(n // 2)
else:
	for num in range(3, 200000, 2):
		if all((not num % i == 0 for i in range(2, int(math.sqrt(num)) + 1))):
			pr.append(int(num))
	found = False
	for p in pr:
		if n % p == 0:
			found = True
			break
	if found:
		n = n - p
	else:
		n = 0
	print(n // 2 + 1)


n = int(input())

def cnt(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	elif n % 2 == 0:
		return n // 2
	divisable = False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			divisable = True
			return 1 + cnt(n - i)
	return 1
print(cnt(n))


import math
n = int(input())
if n % 2 != 0:
	i = 3
	while i <= math.sqrt(n):
		if n % i == 0:
			print(int((n - i) / 2 + 1))
			break
		i += 1
	else:
		print(1)
else:
	print(int(n / 2))


import math

def leastPrimeFactor(n):
	index = n
	for i in range(3, int(math.sqrt(n)) + 1):
		if n % i == 0:
			index = i
			break
	return index
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	print(int((n - leastPrimeFactor(n)) / 2) + 1)


import math

def func(n):
	d = int(math.sqrt(n))
	for i in range(2, d + 1):
		if n % i == 0:
			return i
	return n
n = int(input())
ans = 0
while n % 2:
	ans += 1
	n -= func(n)
print(ans + int(n / 2))


n = int(input())
if n % 2 == 0:
	print(n // 2)
	exit(0)
for x in range(2, int(n ** 0.5 + 1)):
	if n % x == 0:
		print(1 + (n - x) // 2)
		exit(0)
print(1)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	import math
	f = 0
	for i in range(3, int(math.sqrt(n)) + 1):
		if n % i == 0:
			f = 1
			d = i
			break
	if f == 0:
		d = n
	print(1 + (n - d) // 2)


n = int(input())
flag = 0
ans = 0
if n % 2 == 0:
	ans = n / 2
	flag = 1
elif n == 1:
	ans = 1
elif n % 2 == 1:
	for d in range(2, int(n ** 0.5) + 1):
		if n % d == 0:
			ans = 1 + (n - d) / 2
			flag = 1
			break
if flag == 0:
	ans = 1
print(int(ans))


import math
n = int(input())

def primo(l):
	for i in range(2, math.ceil(math.sqrt(l)) + 1):
		if l % i == 0:
			return False
	return True
if n % 2 == 0:
	print(int(n / 2))
	exit()
for i in range(3, math.ceil(math.sqrt(n)) + 1, 2):
	if n % i == 0:
		if primo(i):
			print(int(1 + (n - i) / 2))
			exit()
print(1)


import math

def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
k = 0
i = 2
while i <= math.sqrt(n):
	if n % i == 0:
		k = i
		break
	i += 1
if k == 0:
	print(math.ceil(1 / n))
else:
	print(math.ceil((n - k) / 2 + 1))


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	fl = 1
	for u in range(2, int((n + 1) ** 0.5) + 2):
		if n % u == 0:
			print(1 + (n - u) // 2)
			fl = 0
			break
	if fl:
		print(1)


def ii():
	return int(input())

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

def li():
	return list(mi())
MX = 10 ** 5
n = ii()
if n % 2 == 0:
	ans = n // 2
else:
	c = 3
	ans = 0
	while c <= MX:
		if n % c == 0:
			n -= c
			ans += 1
			break
		c += 1
	if ans:
		ans += n // 2
	else:
		ans = 1
print(ans)


import math
x = int(input())
if x % 2 == 0:
	exit(print(x // 2))
elif x % 3 == 0:
	exit(print((x - 3) // 2 + 1))
else:
	for i in range(5, round(math.sqrt(x)) + 1, 6):
		if x % i == 0:
			exit(print((x - i) // 2 + 1))
		elif x % (i + 2) == 0:
			exit(print((x - (i + 2)) // 2 + 1))
print(1)


import sys
from os import path
if path.exists('input.txt') and path.exists('output.txt'):
	sys.stdout = open('output.txt', 'w')
	sys.stdin = open('input.txt', 'r')

def main():
	n = int(input())
	ans = 0
	while n > 0:
		sm_p = n
		if n % 2 == 0:
			ans += n // 2
			break
		else:
			i = 3
			while i * i <= n:
				if n % i == 0:
					sm_p = i
					break
				i += 2
		n -= sm_p
		ans += 1
	print(ans)
main()


import math
l1 = int(input())
r = 0
if l1 % 2 != 0:
	n = l1
	i = 2
	while i * i <= n:
		if n % i == 0:
			n = i
		i += 1
	l1 -= n
	r += 1
print(int(r + l1 / 2))


import time
import collections
import math

class Time_test:

	def __enter__(self):
		self.enter_time = time.time()

	def __exit__(self, exc_type, exc_val, exc_tb):
		print('Command was executed in', time.time() - self.enter_time)
n = int(input())
counter = 0
if n % 2 == 1:
	for i in range(3, math.floor(math.sqrt(n)) + 1):
		if n % i == 0:
			n -= i
			counter += 1
			break
for i in range(2, math.floor(math.sqrt(n)) + 1):
	if n % i == 0:
		counter += n // i
		n -= n // i * i
		break
if n != 0:
	counter += 1
print(counter)


n = int(input())
res = 0
if n % 2 == 0:
	res = n // 2
	print(res)
	exit(0)
else:
	for i in range(2, int(n ** 0.5 + 1)):
		if n % i == 0:
			res = (n - i) // 2 + 1
			print(res)
			exit(0)
print(1)


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	c = 0
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			c = 1
			k = i
			break
	if c == 0:
		print(1)
	else:
		print(1 + (n - k) // 2)


from sys import stdin

def main():
	N = int(input())
	n = N
	if N % 2:
		primes = erastosthenes(int(N ** 0.5))
		cnt = 1
		for i in primes:
			if not N % i:
				n -= i
				break
		else:
			n = 0
	else:
		cnt = 0
	print(cnt + n // 2)

def erastosthenes(n):
	prime = [0, 1] * ((n + 1) // 2)
	if not n % 2:
		prime += [0]
	(prime[1], prime[2]) = (0, 1)
	i = 3
	while i <= n ** 0.5:
		for j in range(i * i, n + 1, i):
			prime[j] = 0
		i += 2
	prime_list = [2] + [i for i in range(3, n + 1, 2) if prime[i]]
	return prime_list
input = lambda : stdin.readline()
main()


from math import sqrt
N = int(input())
D = int(sqrt(N) + 1)
if N % 2 == 0:
	print(N // 2)
else:
	for i in range(3, D + 1, 2):
		if N % i == 0:
			print(int(1 + (N - i) / 2))
			exit()
	print(1)


n = int(input())
a = [True] * 100006
for i in range(2, 100006):
	if a[i] == True:
		for j in range(i ** 2, 100006, i):
			a[j] = False
count = 1
if n % 2 == 0:
	count = n // 2
if n % 2 != 0:
	for i in range(2, 100006):
		if a[i] == True and n % i == 0:
			count = (n - i) // 2 + 1
			break
print(count)


n = int(input())
import math
i = 3
a = 0
li = []
if n % 2 == 0:
	print(int(n / 2))
else:
	while i <= int(math.sqrt(n)):
		if n % i == 0:
			li.append(i)
			a += 1
			break
		else:
			i += 2
	if a == 0:
		li.append(n)
	if n == li[0]:
		print(1)
	else:
		print(int((n - li[0]) / 2) + 1)


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	count = 0
	while n % 2 != 0:
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				n = n - i
				count += 1
				break
		else:
			count += 1
			n = 1
			break
	if n != 1:
		count += n // 2
	print(count)


n = int(input())

def ss(x):
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			return i
	return x
f = ss(n)
print([n // f, (n - f) // 2 + 1][f != 2])


import math
n = int(input())
l = int(math.sqrt(n)) + 1
is_prime = [True] * l
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, l):
	if is_prime[i]:
		primes.append(i)
		for j in range(i * 2, l, i):
			is_prime[j] = False
c = 0
while n % 2 == 1:
	subtracted = False
	for p in primes:
		if n % p == 0:
			n -= p
			c += 1
			subtracted = True
			break
	if not subtracted:
		n = 0
		c += 1
print(c + n // 2)


def eratosthenes(n):
	sieve = list(range(n + 1))
	sieve[1] = 0
	prime = []
	for i in sieve:
		if i > 0:
			prime.append(i)
			for j in range(i * i, len(sieve), i):
				sieve[j] = 0
	return prime
n = int(input())
s = 0
p = eratosthenes(100000)
if n % 2 == 0:
	print(n // 2)
else:
	for i in p:
		if n % i == 0:
			print(1 + (n - i) // 2)
			exit()
	print(1)


n = int(input())
d = n
i = 2
while i * i <= n:
	div = n // i
	if i * div == n:
		d = i
		break
	i += 1
print(1 + (n - d) // 2)


def minorPrime(n):
	p = 2
	while p * p <= n:
		if n % p == 0:
			return p
		p += 1
	return n
n = int(input())
operations = 0
n -= minorPrime(n)
operations += 1
operations += int(n / 2)
print(operations)


n = int(input())
for i in range(2, n + 1):
	if n % i == 0:
		if i == 2:
			print(n // i)
			return
		else:
			print(1 + (n - i) // 2)
			return
	if i * i > n * 2:
		break
print(1 if n > 0 else 0)


from math import *
n = int(input())
c = 1
for i in range(2, int(sqrt(n)) + 1):
	if n % i == 0 and i == 2:
		c = n // 2
		break
	elif n % i == 0:
		c = 1 + (n - i) // 2
		break
print(c)


import sys
import math

def rint():
	return map(int, sys.stdin.readline().split())
n = int(input())
if n % 2 == 0:
	cnt = n // 2
else:
	for i in range(3, int(math.sqrt(n) + 1)):
		if n % i == 0:
			cnt = 1 + (n - i) // 2
			break
	else:
		cnt = 1
print(cnt)


def f(x):
	global ans
	for d in range(2, int(x ** 0.5) + 1):
		if x % d == 0:
			ans += 1
			return x - d
	ans += 1
	return 0
n = int(input())
if n % 2 == 0:
	ans = n // 2
else:
	ans = 0
	while n % 2 != 0:
		n = f(n)
	ans += n // 2
print(ans)


def f(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n
n = int(input())
ans = 0
if n % 2 == 0:
	print(n // 2)
else:
	a = f(n)
	n -= a
	print(n // 2 + 1)


def find_smallest_div(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return i
	return n

def func(n):
	count = 0
	if n == 0:
		return count
	else:
		d = find_smallest_div(n)
		return 1 + (n - d) // 2
n = int(input())
print(func(n))


from math import *

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

def cins():
	return input.split()

def cino(test=False):
	if not test:
		return int(input())
	else:
		return input()

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

def ssplit():
	return list(input().split())

def printlist(l):
	for i in l:
		print(i, end=' ')

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def main():
	n = cino()
	cnt = 0
	print(1 + (n - smallestDivisor(n)) // 2)
main()


from math import sqrt
n = int(input())
flag = 0

def sieveofEr(n):
	i = 2
	primeno = [False] * n
	l = []
	while i <= n:
		j = i * i
		while j <= n:
			primeno[j - 1] = True
			j = j + i
		i = i + 1
	for i in range(1, len(primeno)):
		if primeno[i] == False:
			l.append(i + 1)
	return l
t = int(sqrt(n))
p = sieveofEr(t)
for i in range(len(p)):
	if n % p[i] == 0:
		flag = 1
		break
if flag == 0:
	print(1)
elif p[i] % 2 == 1:
	print((n - p[i]) // 2 + 1)
else:
	print(n // 2)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
import heapq

def pf(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		else:
			i += 2
	return n
n = int(input())
if not n & 1:
	print(n // 2)
else:
	ans = 0
	x = pf(n)
	while n % 2 != 0:
		n -= x
		if n < 0:
			break
		ans += 1
	print(ans + n // 2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = 0
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = 1
			break
	return ans

def divisor(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return i
	return n
import math
for t in range(1):
	cnt = 0
	n = int(input())
	if n % 2 != 0:
		n -= divisor(n)
		cnt += 1
	print(cnt + n // 2)


import math as m
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	sq = int(m.sqrt(n))
	d = 3
	while d <= sq and n % d != 0:
		d += 1
	if d <= sq:
		print(1 + (n - d) // 2)
	else:
		print(1)


from math import sqrt
n = int(input())
answer = 0
cur = n
for i in range(2, int(sqrt(n)) + 2):
	if n % i == 0:
		if i % 2 == 0:
			answer = n // i
		else:
			answer += 1
			n -= i
			answer += n // 2
		break
if answer == 0:
	print(1)
else:
	print(answer)


def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
resp = 0
while n > 0:
	if n % 2 == 0:
		resp += n // 2
		break
	s = smallestDivisor(n)
	n = n - s
	resp += 1
print(resp)


def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
k = n
print(int((n - smallestDivisor(k)) / 2 + 1))


n = int(input())
import math
import sys
if n % 2 == 0:
	print(n // 2)
	return
xn = math.ceil(math.sqrt(n))
for i in range(2, xn + 2):
	if n % i == 0:
		print((n - i) // 2 + 1)
		return
print(1)


import math
n = int(input())
sub = 0
k = 0
if not n & 1:
	print(n // 2)
	k += 1
for j in range(3, int(math.sqrt(n)) + 1, 2):
	if not n % j:
		n -= j
		sub += 1
	if not n & 1 and n != 0 and (k != 1):
		k += 1
		print(sub + n // 2)
		break
	if n == 0:
		break
if n > 1:
	sub += 1
if k < 1:
	print(sub)


def is_prime(possiblePrime):
	isPrime = True
	for num in range(2, int(possiblePrime ** 0.5) + 1):
		if possiblePrime % num == 0:
			isPrime = False
			break
	return isPrime

def approach3(givenNumber):
	primes = []
	for possiblePrime in range(2, givenNumber):
		if is_prime(possiblePrime):
			if givenNumber % possiblePrime == 0:
				return possiblePrime
n = int(input())
if is_prime(n):
	print(1)
else:
	smallest = approach3(n)
	print(1 + int((n - smallest) / 2))


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	pr = -1
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		if n % i == 0:
			pr = i
			break
	if pr == -1:
		pr = n
	x = n // pr
	m = (x - 1) * pr
	print(1 + m // 2)


import math

def primeFactors(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	if n > 2:
		return n
n = int(input())
k = primeFactors(n)
if k == 2:
	print(n // k)
elif k == n:
	print(1)
else:
	n -= k
	print(1 + n // 2)


from math import sqrt, ceil

def f(n):
	for i in range(2, int(sqrt(n)) + 2):
		if n % i == 0:
			return i
	return n
n = int(input())
cnt = 0
while n % 2 != 0:
	n -= f(n)
	cnt += 1
print(cnt + n // 2)


n = int(input())
ans = 0
if n % 2 != 0:
	i = 3
	while n % i != 0 and i * i < n:
		i += 2
	if n % i != 0:
		i = n
	n -= i
	ans = 1
ans += n // 2
print(ans)


n = int(input())

def getFirstPrime(n):
	sqrt = int(n ** (1 / 2)) + 1
	for k in range(3, sqrt, 2):
		if n % k == 0:
			return k
	return n
if n % 2 == 0:
	print(int(n / 2))
else:
	n = n - getFirstPrime(n)
	print(int(n / 2) + 1)


import math
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	a = 0
	achou = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			a = i
			achou = True
			break
	if achou:
		print(int((n - a) / 2 + 1))
	else:
		print(1)


from sys import stdin, stdout
from math import *

def nStep(n):
	if n == 0:
		return 0
	if n == 2:
		return 1
	for i in range(2, floor(sqrt(n) + 2), 1):
		if n % i == 0:
			if i == 2:
				return floor(n / 2)
			else:
				return 1 + nStep(n - i)
	return 1

def main():
	n = int(stdin.readline())
	stdout.write(str(nStep(n)))
	return 0

def __starting_point():
	main()
__starting_point()


from math import sqrt
n = int(input())
compound = {}
compound[0] = 1
compound[1] = 1
compound = [0] * 100000
for i in range(2, int(sqrt(100000)) + 1):
	for p in range(2 * i, 100000, i):
		compound[p] = 1

def min_div(x):
	for i in range(2, 100000):
		if not compound[i] and (not x % i):
			return i
	return x
if n % 2:
	print((n - min_div(n)) // 2 + 1)
else:
	print(n // 2)


import math
n = int(input())

def func(n):
	isprime = True
	count = 0
	if n % 2 == 0:
		count = n // 2
		return count
	z = int(math.floor(math.sqrt(n))) + 1
	for i in range(2, z):
		if n % i == 0:
			isprime = False
			break
	if isprime:
		return 1
	n = n - i
	count = 1 + n // 2
	return count
print(func(n))


A = [False for _ in range(10 ** 6 + 40)]
n = int(input())
f = 0
for i in range(2, len(A)):
	if A[i] == False:
		if n % i == 0:
			f = i
			break
		j = 2 * i
		while j < len(A):
			A[j] = True
			j += i
if f == 0:
	print(1)
else:
	print((n - f) // 2 + 1)


n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	d = n
	ct = 3
	while ct ** 2 <= n:
		if n % ct == 0:
			d = ct
			break
		ct += 2
	print(1 + int((n - d) / 2))


n = int(input())
res = 0
flag = False
for d in range(2, int(n ** 0.5) + 1):
	if n % d == 0:
		flag = True
		n -= d
		res += 1
		break
if flag:
	res += int(n / 2)
else:
	res = 1
print(res)


def sol(x):
	if x % 2 == 0:
		return 2
	else:
		n = 3
		while n * n <= x:
			if x % n == 0:
				return n
			else:
				n += 2
		return x
x = int(input())
j = x
ans = 0
while x % 2 == 1:
	x -= sol(x)
	ans += 1
print(ans + x // 2)


n = int(input())
i = 1
k = 3
while k != 0 and i <= n ** 0.5:
	i += 1
	k = n % i
if n % i != 0:
	print(1)
else:
	n = n - i
	print(n // 2 + 1)


from sys import stdin, stdout
from itertools import accumulate
N = int(input())
if N % 2 == 0:
	print(N // 2)
	quit()
found_prime = 0
for i in range(2, 100001):
	if i * i > N:
		break
	elif N % i == 0:
		found_prime = i
		break
if found_prime == 0:
	print(1)
else:
	N -= found_prime
	print(1 + N // 2)


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

def it():
	return int(input())
n = it()
if n & 1 == 0:
	print(n // 2)
else:
	i = 2
	while i * i <= n and n % i:
		i += 1
	if i * i > n:
		n = i
	print((n - i) // 2 + 1)


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
ans = 0
if isPrime(n):
	ans = 1
elif n % 2 == 0:
	ans = n // 2
else:
	for i in range(n // 3 + 2):
		if i % 2 == 0:
			continue
		elif isPrime(i) and n % i == 0:
			new = n - i
			ans = new // 2 + 1
			break
print(ans)


n = int(input())
if n % 2 == 0:
	print(n // 2)
elif n ** 0.5 < 3:
	print(1)
else:
	boolean = 0
	for i in range(3, int(n ** 0.5) + 1, 2):
		div = n / i
		if div % 1 == 0:
			print((n - i) // 2 + 1)
			boolean = 1
			break
	if boolean == 0:
		print(1)


import math
N = int(input())
if N % 2 == 0:
	print(N // 2)
else:
	p = N
	for i in range(2, int(math.sqrt(N)) + 1):
		if N % i == 0:
			p = i
			break
	print((N - p) // 2 + 1)


import math

def find_first_prime_divisor(n):
	if n % 2 == 0:
		return 2
	for p in range(3, math.ceil(math.sqrt(n)) + 1, 2):
		if n % p == 0:
			return p
	return n
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	n -= find_first_prime_divisor(n)
	print(n // 2 + 1)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	mini = 0
	for i in range(3, int(n ** 0.5) + 1):
		if n % i == 0:
			mini = i
			break
	if mini == 0:
		print(1)
	else:
		print((n - mini) // 2 + 1)


import math

def prime(n):
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			return i
		elif i == 2:
			i += 1
		else:
			i += 2
	return n
n = int(input())
r = 0
while n != 0:
	d = prime(n)
	if d == n:
		r += 1
		break
	elif n % 2 == 0:
		r = r + n // 2
		break
	else:
		n -= d
		r += 1
print(r)


from math import sqrt

def SPD(n) -> int:
	if n % 2 == 0:
		return 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	return -1
n = int(input())
cnt = 0
if SPD(n) == -1:
	print(1)
	exit(0)
while True:
	if n % 2 == 0:
		print(n // 2 + cnt)
		exit(0)
	else:
		n -= SPD(n)
		cnt += 1


n = int(input())
i = 2
while i * i <= n:
	if n % i == 0:
		break
	i += 1
if i * i > n:
	print(1)
elif i % 2 == 1 and n // i % 2 == 1:
	print(1 + (n - i) // 2)
else:
	print(n // i)


import math

def get_number_of_substractions(n):
	after_first_sub = n - find_first_divisor(n)
	return after_first_sub // 2 + 1

def find_first_divisor(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
result = get_number_of_substractions(n)
print(result)


import math
n = float(input())
result = 0
menor = -1
r = int(math.sqrt(n))
for i in range(2, r + 1):
	if n % i == 0:
		result += 1
		menor = i
		n = n - i
		break
if menor == -1:
	result = 1
else:
	result = result + int(n / 2)
print(result)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	lp = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			lp = i
			break
		i += 1
	print((n - lp) // 2 + 1)


def prime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		if n % i == 0 and n % (n // i) == 0:
			return False
		i += 1
	return True

def sieve(n):
	dp = [False] * (n + 2)
	dp[0] = True
	dp[1] = True
	i = 2
	prime = []
	while i <= n:
		if not dp[i]:
			prime.append(i)
			for j in range(2 * i, n + 2, i):
				dp[j] = i
		i += 1
	return prime
primes = sieve(10 ** 5)
n = int(input())
if prime(n):
	print(1)
else:
	for i in primes:
		if n % i == 0:
			print(1 + (n - i) // 2)
			break


n = int(input())
i = 2
d = n
while i * i <= n:
	if n % i == 0:
		d = i
		break
	i += 1
print(1 + (n - d) // 2)


n = int(input())
subs = 0
while n != 0:
	if n % 2 == 0:
		subs += n // 2
		break
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			n = n - i
			subs = 1
			break
	if n > 0 and n % 2 == 0:
		subs += n // 2
		break
	elif n > 0:
		subs += 1
		break
print(subs)


n = int(input())
response = 0
while n % 2 != 0:
	x = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			x = i
			break
		i += 1
	n -= x
	response += 1
response += n / 2
print(int(response))


from math import sqrt
from itertools import count, islice

def isPrime(n):
	return n > 1 and all((n % i for i in islice(count(2), int(sqrt(n) - 1))))

def primes_method4(n):
	out = list()
	out.append(2)
	for num in range(3, n + 1, 2):
		if all((num % i != 0 for i in range(2, int(num ** 0.5) + 1))):
			out.append(num)
	return out

def div(n, a):
	if n == 0:
		return 0
	elif n % 2 == 0:
		return n // 2
	elif isPrime(n):
		return 1
	else:
		for i in a:
			if n % i == 0:
				break
		return 1 + div(n - i, a)
n = int(input())
arr = primes_method4(100000)
anws = div(n, arr)
print(anws)


n = int(input())
i = 2
while i * i < n and n % i != 0:
	i += 1
if i * i > n:
	i = n
print(1 + (n - i) // 2)


n = int(input())
ans = 0
while n != 0:
	if n % 2 == 0:
		ans += n // 2
		break
	ans += 1
	p = 3
	tmp = int(n ** 0.5)
	while p < n:
		if n % p == 0:
			break
		if p > tmp:
			p = n
		else:
			p += 2
	n -= p
print(ans)


n = int(input())
i = 2
while i * i <= n:
	if n % i == 0:
		print(1 + (n - i) // 2)
		exit(0)
	i += 1
print(1)


import math

def find(n):
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
count = 0
while n % 2 != 0:
	n = n - find(n)
	count += 1
print(count + n // 2)


from collections import deque
from math import sqrt, ceil

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())

def isprime(n):
	if n == 1:
		return 0
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return 0
	return 1
n = ii()
if isprime(n):
	print('1')
elif n % 2 == 0:
	print(n // 2)
else:
	c = 0
	a = []
	b = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0 and isprime(i):
			a.append(i)
		if i != n // i and isprime(n // i):
			b.append(n // i)
	if len(a) != 0:
		x = min(a)
	else:
		x = min(b)
	n -= x
	print(n // 2 + 1)


def prime(n):
	i = 1
	cont = 0
	while i * i <= n:
		if n % i == 0:
			cont += 1
			if i * i != n:
				cont += 1
		i += 1
	return cont
n = int(input())
primes = prime(n)
nprimo = 3
sub = 0
if n % 2 == 0:
	sub = n // 2
elif primes > 2:
	while n > 0:
		if n % 2 == 0:
			break
		if n % nprimo == 0:
			n = n - nprimo
			sub += 1
		else:
			nprimo += 1
	sub += n // 2
else:
	sub = 1
print(sub)


from math import sqrt

def kek(n):
	if n == 2:
		return 2
	for i in range(2, int(sqrt(n)) + 2):
		if n % i == 0:
			return i
	return n
n = int(input())
k = 0
while n > 0:
	if n % 2 == 0:
		k += n // 2
		break
	k += 1
	n -= kek(n)
print(k)


n = int(input())
i = 2
m = 0
while n % i != 0 and i * i <= n:
	i += 1
if n % i == 0:
	m += 1
	n -= i
	m += n // 2
	print(m)
else:
	print(1)


def func():
	global x
	if x % 2 == 0:
		print(x // 2)
	else:
		count = 0
		flag = True
		for i in range(3, int(x ** (1 / 2)) + 1, 2):
			if x % i == 0:
				x -= i
				count += 1
				flag = False
				break
		if flag:
			print(1)
			return
		else:
			print(count + x // 2)
x = int(input())
func()


import math

def f(n):
	if n % 2 == 0:
		return n // 2
	s = int(math.sqrt(n))
	mf = n
	for i in range(3, s + 1, 2):
		if n % i == 0:
			mf = i
			break
	return 1 + (n - mf) // 2
n = int(input())
print(f(n))


import math

def prime(n):
	max_div = math.floor(math.sqrt(n))
	for i in range(3, 1 + max_div, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
j = 0
while True:
	if n == 0:
		print(j)
		break
	elif n % 2 == 0:
		print(j + n // 2)
		break
	else:
		n = n - prime(n)
		j = j + 1


pr = [1] * 300001
(pr[0], pr[1]) = (0, 0)
primes = []
for i in range(2, 300001):
	if pr[i] == 1:
		primes.append(i)
		for j in range(i * i, 100001, i):
			pr[j] = 0

def prime(n):
	for i in range(2, int(n ** 0.5) + 2):
		if n % i == 0:
			return False
	return True

def dope(n):
	if n < 2 or n > 10000000000.0:
		return 1 // 0
	if prime(n):
		return 1
	for i in primes:
		if n % i == 0:
			if i == 2:
				return n // i
			return 1 + dope(n - i)
	return 1 // 0
print(dope(int(input())))


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	import math
	res = n
	max_val = int(math.sqrt(n))
	for i in range(3, max_val + 1, 2):
		if n % i == 0:
			res = i
			break
	n -= res
	print(1 + n // 2)


def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
m = int(input())
n = int(m)
if m % 2 == 0:
	print(m // 2)
else:
	print((m - prime_factors(m)[0]) // 2 + 1)


def sd(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
k = sd(n)
if n % 2 == 0:
	print(int(n // 2))
else:
	p = n - k
	print(int(p // 2) + 1)


n = int(input())
p = 2
flag = False
while p * p <= n:
	if n % p == 0:
		flag = True
		break
	p += 1
if flag:
	n = n - p
	print(1 + n // 2)
else:
	print(1)


def go():
	n = int(input())
	if n % 2 == 0:
		return n // 2
	a = n
	c = 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			a = i
			break
		i += 1
	n -= a
	return 1 + n // 2
print(go())


n = int(input())
if n == 0:
	print(0)
	exit()
k = 0
while n % 2 != 0:
	flag = 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			flag = 1
			break
	if flag == 1:
		n = n - i
	else:
		n = 0
	k += 1
print(k + n // 2)


n = int(input())
flag = 0
i = 2
while i ** 2 <= n:
	if n % i == 0:
		flag = 1
		break
	i += 1
cnt = 0
if flag == 0:
	print(1)
else:
	print(1 + (n - i) // 2)


from math import ceil
n = int(input())
i = 2
while i <= n ** 0.5:
	if n % i == 0:
		break
	i += 1
else:
	print(1)
	exit()
if i == 2:
	print(n // i)
	exit()
print(1 + i * (n // i - 1) // 2)


import math
x = int(input())
inicial = x
cnt = 0
while x > 0:
	if x % 2 == 0:
		cnt += int(x / 2)
		x = 0
		break
	else:
		for i in range(3, math.ceil(math.sqrt(x)) + 1, 2):
			if x % i == 0:
				x -= i
				cnt += 1
				break
		if inicial == x:
			cnt = 1
			x = 0
print(cnt)


n = int(input())
d = 2
step = 0
while n != 0 and d <= 100000:
	if n % d == 0:
		step = step + 1
		n = n - d
		break
	else:
		d = d + 1
		continue
if d == 100001:
	step = 1
	print(step)
else:
	step = n // 2 + step
	print(step)


from math import *
a = int(input())
for i in range(2, floor(sqrt(a)) + 1):
	if a % i == 0:
		print(int((a - i) / 2) + 1)
		exit()
print(1)


from math import ceil
a = int(input())
steps = 0

def minprime(x):
	for i in range(2, ceil(x ** 0.5) + 1):
		if x % i == 0:
			return i
	return x
while a != 0:
	t = minprime(a)
	if t == 2:
		steps += a // t
		a = 0
	else:
		a -= t
		steps += 1
print(steps)


import math

def subtractions(n):
	if n % 2 == 0:
		return n // 2
	i = 3
	while i <= math.sqrt(n):
		if n % i == 0:
			return 1 + (n - i) // 2
		i += 1
	return 1
n = int(input())
print(subtractions(n))


import math
n = int(input())
r = int(math.sqrt(n))
b = []
for i in range(1, r + 1):
	if n % i == 0:
		if i == n / i:
			b.append(i)
		else:
			b.append(i)
			b.append(int(n / i))
b.remove(1)
print(int(1 + (n - min(b)) / 2))


import math
n = int(input())
subs = 0
while n > 0:
	if n % 2 == 0:
		subs += n // 2
		n = 0
	else:
		sq = int(math.sqrt(n))
		found = False
		for i in range(2, sq + 1):
			if n % i == 0:
				found = True
				break
		if found:
			subs += 1
			n -= i
		else:
			subs += 1
			n = 0
print(subs)


import sys, threading
sys.setrecursionlimit(10 ** 6)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
if isPrime(n):
	print(1)
else:
	i = 2
	while 1:
		if n % i == 0:
			break
		i += 1
	n -= i
	print(int(n / 2) + 1)


n = int(input())
if not n % 2:
	print(n // 2)
else:

	def primes_sieve(limit):
		a = [True] * limit
		a[0] = a[1] = False
		for (i, isprime) in enumerate(a):
			if isprime:
				for n in range(i * i, limit, i):
					a[n] = False
		return a
	sieve = primes_sieve(1000100)
	for i in range(len(sieve)):
		if sieve[i]:
			if not n % i:
				print((n - i) // 2 + 1)
				exit()
	print(1)


import math

def function(n):
	if n == 3:
		return 1
	if n % 2 == 0:
		return int(n / 2)
	for i in range(2, math.floor(math.sqrt(n)) + 1):
		if n % i == 0:
			return int((n - i) / 2) + 1
	return 1
n = int(input())
print(function(n))


import math
n = int(input())
li = []
if n % 2 == 0:
	print(n // 2)
else:
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			li.append(i)
			li.append(n // i)
	if len(li) == 2:
		print((n - li[1]) // 2 + 1)
	else:
		print((n - li[2]) // 2 + 1)


n = int(input())

def PrimeList(limit):
	Plist = []
	for i in range(2, limit + 1):
		divcheck = False
		for j in Plist:
			if j * j > i:
				break
			if i % j == 0:
				divcheck = True
				break
		if divcheck == False:
			Plist.append(i)
	return Plist
L = PrimeList(10 ** 5)
count = 0
primecheck = True
for p in L:
	if p * p > n:
		break
	if n % p == 0:
		smallest = p
		primecheck = False
		break
if primecheck == True:
	smallest = n
print(1 + int((n - smallest) / 2))


n = int(input())
k = int(n ** 0.5) + 1
f = False
for i in range(2, k + 1):
	if n % i == 0:
		f = True
		break
if not f:
	print(1)
	exit(0)
b = 0
for i in range(2, k + 1):
	if n % i == 0:
		b = i
		break
if b == 2:
	print(n // 2)
else:
	print(1 + (n - b) // 2)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		n = I()
		if n % 2 == 0:
			rr.append(n // 2)
		else:
			k = n
			for i in range(3, int(n ** 0.5) + 3, 2):
				if n % i == 0:
					k = i
					break
			n -= k
			rr.append(n // 2 + 1)
	return JA(rr, '\n')
print(main())


entero = int(input())
div = 2
while div * div < entero and entero % div:
	div += 1
if div * div > entero:
	div = entero
print(1 + (entero - div) // 2)


def divis(n):
	l = []
	for i in range(2, int(n ** 0.5) + 1):
		if not n % i:
			return i
	return n
n = int(input())
print(1 + (n - divis(n)) // 2)


import math

def list_primes_upto(upto: int):
	uptop1 = upto + 1
	uptom1 = upto - 1
	pcl = [True for x in range(uptop1)]
	lprimes = []
	if upto >= 2:
		lprimes.append(2)
	if upto >= 3:
		lprimes.append(3)
	i = 5
	while i < uptom1:
		ix2 = i * 2
		if pcl[i]:
			lprimes.append(i)
			for k in range(i * i, uptop1, ix2):
				pcl[k] = False
		ip2 = i + 2
		ip2x2 = ip2 * 2
		if pcl[ip2]:
			lprimes.append(ip2)
			for k in range(ip2 * ip2, uptop1, ip2x2):
				pcl[k] = False
		i += 6
	if i <= upto:
		ix2 = i * 2
		if pcl[i]:
			lprimes.append(i)
			for k in range(i * i, uptop1, ix2):
				pcl[k] = False
	return lprimes
n = int(input())
lp = list_primes_upto(int(math.sqrt(n)) + 1)
subs = 0
pi = 0
while n != 0 and pi < len(lp):
	if n % lp[pi] == 0:
		if pi == 0:
			subs += n // 2
			n = 0
		else:
			n -= lp[pi]
			subs += 1
			pi = 0
	else:
		pi += 1
if n != 0:
	subs += 1
print(subs)


def sieve(n):
	arr = [1] * (n + 1)
	arr[0] = 0
	arr[1] = 0
	for x in range(2, int(n ** 0.5) + 1):
		if arr[x] == 1:
			arr[x * x::x] = [0 for i in arr[x * x::x]]
	return [x for x in range(len(arr)) if arr[x] == 1]

def smallest_div(n, primes):
	for x in primes:
		if n % x == 0:
			return x
	return n

def solve():
	n = int(input())
	primes = sieve(int(n ** 0.5) + 1)
	res = 0
	while n > 0:
		n -= smallest_div(n, primes)
		res += 1
		while n > 0 and n % 2 == 0:
			res += n // 2
			n = 0
	print(res)
solve()


import sys
import math
number = int(input())
if number % 2 == 0:
	print(number // 2)
	sys.exit(0)
first_div = -1
counter = 3
divisors = []
for i in range(1, int(math.sqrt(number)) + 1):
	if number % i == 0:
		divisors.append(i)
		divisors.append(number // i)
if len(divisors) == 2:
	print(1)
else:
	print((number - divisors[2]) // 2 + 1)


import math

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
result = 0
x = 0

def go(k):
	global result, x
	if k == 0:
		return
	if k % 2 == 0:
		print(k // 2)
		return
	else:
		if isPrime(k):
			print(1)
			return
		for i in range(3, int(math.sqrt(n)) + 1):
			if isPrime(i) and k % i == 0:
				x = i
				break
		print(1 + (n - x) // 2)
go(n)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

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

def prime(n):
	for i in range(2, int(sqrt(n)) + 2):
		if not n % i:
			return False
	return True
n = int(input())
if not n % 2:
	print(n // 2)
else:
	ele = n
	for i in range(3, int(sqrt(n)) + 2):
		if n % i == 0 and prime(i):
			ele = i
			break
	print((n - ele) // 2 + 1)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	i = 3
	ans = 0
	f = 0
	while i * i <= n:
		if n % i == 0:
			f = 1
			n -= i
			ans += 1
			break
		i += 1
	if f:
		ans += n // 2
		print(ans)
	else:
		print(1)


from math import sqrt

def smallest_prime(x):
	if x % 2 == 0:
		return 2
	else:
		n = int(sqrt(x) + 1)
		for i in range(3, n, 2):
			if x % i == 0:
				return i
	return x
num = int(input())
count = 0
while smallest_prime(num) != 2:
	count += 1
	num -= smallest_prime(num)
print(count + num // 2)


import math

def small_prime_div(n):
	for x in range(2, math.floor(math.sqrt(n)) + 1):
		if n % x == 0:
			return x
	return n
n = int(input())
print(1 + (n - small_prime_div(n)) // 2)


n = int(input())
import math
m = int(math.sqrt(n))
a = [False, False] + [True] * (m - 1)
primes = []
for i in range(2, m + 1):
	if a[i]:
		primes.append(i)
		for j in range(2 * i, m + 1, i):
			a[j] = False
c = 0
while n != 0:
	p = n
	for i in primes:
		if n % i == 0:
			p = i
			break
	n -= p
	c += 1
	if n % 2 == 0:
		c += n // 2
		break
print(c)


import sys
from math import ceil, sqrt
input = sys.stdin.readline
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	prime = n
	for i in range(2, ceil(sqrt(n)) + 1):
		if n % i == 0:
			prime = i
			break
	print(1 + int((n - prime) / 2))


import sys
input = sys.stdin.readline
from math import *
n = int(input())
for i in range(2, int(sqrt(n)) + 1):
	if n % i == 0 and i == 2:
		print(n // i)
		exit(0)
	if n % i == 0:
		print(1 + (n - i) // 2)
		exit(0)
print(1)


n = int(input())
import math
n1 = n
i = []
for x in range(100001):
	i.append(True)
(i[0], i[1]) = (False, False)
for x in range(2, int(math.sqrt(100000))):
	if i[x]:
		for xx in range(2 * x, 100001, x):
			i[xx] = False
o = []
for x in range(100001):
	if i[x]:
		o.append(x)
p = False
if n % 2 == 0:
	print(n // 2)
else:
	for x in o:
		if n >= x and n % x == 0:
			n -= x
			p = True
			break
		elif n < x:
			break
	if not p and n1 > 100000:
		print(1)
	else:
		print(1 + n // 2)


while True:
	try:
		prime = []
		mark = [0] * (10 ** 6 + 2)

		def seive():
			prime.append(2)
			N = 10 ** 6
			for i in range(3, N + 1, 2):
				if not mark[i]:
					prime.append(i)
					if i * i <= N:
						j = i * i
						while j <= N:
							mark[j] = 1
							j += i * 2

		def solution(n):
			if n & 1:
				d = n
				i = 3
				while i * i <= n:
					if n % i == 0:
						d = i
						break
					i += 1
				n -= d
				print(1 + n // 2)
			else:
				print(n // 2)
		if __name__ == '__main__':
			n = int(input())
			solution(n)
	except EOFError:
		break


from math import sqrt

def nam(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return i
	return n
n = int(input())
n -= nam(n)
if n != 0:
	print(1 + n // 2)
else:
	print(1)


n = int(input())
root = int(n ** 0.5)
result = 1
for i in range(2, root + 1):
	if n % i == 0:
		result += (n - i) // 2
		break
print(result)


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	ct = 1
	for i in range(2, int((n + 1) ** 0.5) + 2):
		if n % i == 0:
			print(1 + (n - i) // 2)
			ct = 0
			break
	if ct:
		print(1)


import math
n = int(input())
found = 0
for i in range(2, int(math.sqrt(n)) + 1):
	if n % i == 0:
		print((n - i) // 2 + 1)
		found = 1
		break
if found == 0:
	print(1)


from math import *
a = int(input())
t = []
for i in range(2, int(a ** 0.5) + 1):
	if a % i == 0:
		t.append(i)
if a % 2 == 0:
	print(int(a / 2))
elif t == []:
	print(1)
else:
	print(1 + int((a - t[0]) / 2))


def mind(n):
	d = 3
	while d * d <= n:
		if n % d == 0:
			return d
		d += 1
	return n
n = int(input())
if n == 0:
	print(0)
elif n % 2 == 0:
	print(n // 2)
else:
	res = mind(n)
	n -= res
	print(n // 2 + 1)


def main():
	n = int(input())
	if n % 2 == 0:
		print(n // 2)
		return 0
	for i in range(3, 10 ** 5):
		if n % i == 0:
			print(1 + (n - i) // 2)
			return 0
	print('1')
main()


n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	prime = 3
	while prime * prime < n:
		if n % prime == 0:
			break
		else:
			prime += 2
	if n % prime != 0:
		prime = n
	answer = int((n - prime) / 2)
	answer += 1
	print(answer)


from math import sqrt
n = int(input())
subs = 0
if n % 2 == 0:
	subs += n // 2
else:
	divisor = -1
	for i in range(3, int(sqrt(n) + 2)):
		if n % i == 0:
			divisor = i
			break
	if divisor < 0:
		subs = 1
	else:
		n -= divisor
		subs += 1
		subs += n // 2
print(subs)


from math import *
from sys import stdin, stdout
z = int(stdin.readline())
if z % 2 == 0:
	stdout.write(str(z // 2))
else:
	for i in range(2, ceil(sqrt(z)) + 1):
		if z % i == 0:
			stdout.write(str(1 + (z - i) // 2))
			exit()
	stdout.write('1')


from math import sqrt
sol = 0
n = int(input())
while n % 2 != 0:
	ok = 0
	for i in range(3, min(int(sqrt(n) + 2), n + 1)):
		if n % i == 0:
			n = n - i
			sol = sol + 1
			ok = 1
			break
	if ok == 0:
		n = 0
		sol = sol + 1
		break
print(n // 2 + sol)


n = int(input())
count = 0
while n:
	if not n & 1:
		count += n >> 1
		n = 0
	else:
		r = round(n ** 0.5) + 1
		for i in range(3, r, 2):
			if n % i == 0:
				count += 1
				n -= i
				break
		else:
			count += 1
			n = 0
print(count)


n = int(input())
l = [0] * 100001
l[0] = -1
l[1] = -1
t = []
flag = 0
for i in range(2, 100001 // 2):
	if l[i] != -1:
		for j in range(2 * i, 100001, i):
			l[j] = -1
for i in range(2, 100001):
	if l[i] != -1:
		t.append(i)
for _ in t:
	if n % _ == 0:
		n -= _
		flag = 1
		break
if flag == 0:
	print(1)
else:
	print(n // 2 + 1)


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N,) = getIntList()
if N % 2 == 0:
	print(N // 2)
	sys.exit()
for i in range(2, 110000):
	if N % i == 0:
		print((N - i) // 2 + 1)
		sys.exit()
print(1)


import itertools as it
import functools
import operator
import collections
import math
import sys

def pseudo_prime():
	yield 3
	yield 5
	yield 7
	i = 11
	while True:
		yield i
		yield (i + 2)
		i += 4

def solve(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n % 2 == 0:
		return n // 2
	pseudo_primes = it.takewhile(lambda k: k < int(n ** 0.5 + 1), pseudo_prime())
	for d in pseudo_primes:
		if n % d == 0:
			res = d
			break
	else:
		res = n
	return 1 + solve(n - res)

def main():
	n = int(input())
	result = solve(n)
	print(result)
main()


def isPrime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
subtractions = 0
if n % 2 == 0:
	subtractions = n // 2
elif isPrime(n):
	subtractions = 1
else:
	i = 2
	while i * i <= n:
		if n % i == 0 and isPrime(i):
			d = i
			break
		i += 1
	n -= d
	subtractions = n // 2 + 1
print(subtractions)


n = int(input())
sub = 0

def smallprime(x):
	for i in range(2, int(pow(x, 1 / 2)) + 1):
		if x % i == 0:
			return i
	return x

def dsub(x):
	global sub
	if x == 0:
		print(int(sub))
		return
	if x % 2 == 0:
		sub = sub + x / 2
		print(int(sub))
		return
	else:
		p = smallprime(x)
		sub = sub + 1
		dsub(x - p)
dsub(n)


import math

def find(n):
	if n == 2:
		return 2
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			return i
	return n
n = int(input())
lol = 0
kek = 2
while n > 0:
	if n % 2 == 0:
		lol += n // 2
		break
	f = find(n)
	lol += 1
	n -= f
print(lol)


from math import *

def prmfct(n):
	li = []
	while n % 2 == 0:
		li.append(2)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			li.append(int(i))
			n = int(n / i)
	if n > 2:
		li.append(int(n))
	return li
n = int(input())
ab = min(prmfct(n))
cn = 1
n = n - ab
cn += n / 2
print(int(cn))


import math
n = int(input())

def my(n):
	xx = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				xx.append(n / i)
	for divisor in reversed(xx):
		yield divisor
all_div = my(n)

def get():
	for elem in all_div:
		if len(list(my(elem))) == 2:
			return elem
if n % 2 == 0:
	print(int(n / 2))
else:
	print(int(1 + (n - get()) / 2))


import math
temp = 0
flag = 0
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
else:
	for i in range(2, int(math.sqrt(n) + 1) + 1):
		if n % i == 0:
			temp = i
			flag = 1
			break
	if flag == 0:
		temp = n
	ans = (n - temp) / 2
	ans = ans + 1
	print(int(ans))


import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, gcd, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

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

def instr():
	s = input()
	return list(s[:len(s)])

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

def smallest_divisor(n):
	limit = int(sqrt(n) + 1)
	for i in range(2, limit + 2):
		if n % i == 0:
			return i
	return n
n = inp()
res = 0
d = smallest_divisor(n)
res = 1 + (n - d) // 2
print(res)


from math import sqrt

def check_prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return 0
	else:
		return 1

def smallest_prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if check_prime(i):
			if n % i == 0:
				return i
	else:
		return n
n = int(input())
count = 0
while n != 0:
	if n % 2 == 0:
		count = count + n // 2
		break
	d = smallest_prime(n)
	n = n - d
	count += 1
print(count)


def first_factor(n):
	for num in range(2, int(n ** 0.5) + 1):
		if n % num == 0:
			return num
	return n
a = int(input())
result = 0
now = a
b = a
while a != 0:
	if b != 2:
		b = first_factor(a)
		a -= b
		result += 1
	else:
		result += a // b
		break
print(result)


n = int(input())
m = n
count = 0
while n > 0:
	for i in range(2, min(m, int(n ** 0.5) + 2)):
		if n % i == 0:
			m = i
			break
	if m == 2:
		count += n // 2
		break
	n -= m
	count += 1
print(count)


from math import *
n = int(input())
ans = 0
g = int(sqrt(n) // 1) + 1
l = [0] * g
l[0] = 1
l[1] = 1
d = []
for i in range(2, g):
	if l[i] == 0:
		for j in range(i + i, g, i):
			l[j] = 1
		d.append(i)
k = 0
while n:
	flag = 0
	if n % 2 == 0:
		ans += n // 2
		n = 0
		break
	for i in d:
		if n % i == 0:
			n -= i
			ans += 1
			flag = 1
			break
	if flag == 0:
		break
if ans == 0:
	ans = 1
print(ans)


n = int(input())
for i in range(2, n):
	if n % i == 0:
		print(int((n - i) / 2 + 1))
		raise SystemExit
	if i > 1000000:
		break
print(1)


x = eval(input())
i = 2
sum = 0
flag = True
if x % 2 == 0:
	print(int(x / 2))
else:
	while i <= x ** (1 / 2):
		if x % i == 0:
			sum = int((x - i) / 2 + 1)
			flag = False
			break
		else:
			i += 1
	if flag:
		print(1)
	else:
		print(sum)


def isqrt(n):
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def find_divisor(n):
	if n % 2 == 0:
		return 2
	for i in range(3, isqrt(n) + 1, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
print(1 + (n - find_divisor(n)) // 2)


n = int(input())
done = 0
if n % 2 == 0:
	print(int(n / 2))
else:
	for divisor in range(3, int(n ** 0.5) + 1):
		if n % divisor == 0:
			print(int((n - divisor) / 2 + 1))
			done = 1
			break
	if done == 0:
		print(1)


def algo():
	n = int(input())
	i = 0
	while n > 0:
		if n % 2 == 0:
			i += int(n / 2)
			n = 0
		else:
			p = 3
			while n % p != 0 and p < n ** (1 / 2) + 1:
				p += 2
			n -= p
			i += 1
			if p > n ** (1 / 2) + 1:
				n = 0
				i = 1
	print(i)
algo()


import math

def is_prime(n):
	if n == 2:
		return True
	elif n % 2 == 0 or n == 1:
		return False
	max_divisor = math.floor(math.sqrt(n))
	for d in range(3, 1 + max_divisor, 2):
		if n % d == 0:
			return False
	return True
n = int(input())
if n % 2 == 0:
	print(int(n / 2))
elif is_prime(n):
	print(1)
else:
	for i in range(3, n + 1):
		if n % i == 0:
			print(int(1 + (n - i) / 2))
			break


import math
n = int(input())

def rec(n: int):
	if n == 0:
		return 0
	if n % 2 == 0:
		return n / 2
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			return 1 + rec(n - i)
	return 1
print(int(rec(n)))


from typing import Dict, List, Tuple

def input_lst() -> List[int]:
	return [int(x) for x in input().split()]

def print_out(res: List[int]):
	print(' '.join([str(x) for x in res]))

def main():
	(n,) = (int(x) for x in input().split())
	sieve = list(range(int(n ** 0.5) + 1))
	if n // 2 == n / 2:
		print(n // 2)
		return
	sieve[1] = 0
	for i in sieve:
		if i > 1:
			if n / i == n // i:
				print((n - i) // 2 + 1)
				return
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	print(1)
main()


from math import sqrt

def get_int():
	from sys import stdin
	return int(stdin.readline().replace('\n', ''))

def smallest_prime_factor(n):
	from math import sqrt
	if n % 2 == 0:
		return 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	if n > 2:
		return n

def algo(n):
	subtractions = 0
	spf = smallest_prime_factor(n)
	n -= spf
	subtractions += 1
	if n != 0:
		multiple = int(n / 2)
		subtractions += multiple
	return subtractions
n = get_int()
print(algo(n))


from math import sqrt
n = int(input())
cnt = 0
while n > 0:
	if n % 2 == 0:
		cnt += n // 2
		break
	cnt += 1
	for dv in range(2, int(sqrt(n)) + 1):
		if n % dv == 0:
			n -= dv
			break
	else:
		n = 0
print(cnt)


import math
N = int(input())
c = 0
while N % 2 and N != 0:
	f = 1
	for i in range(2, math.ceil(N ** 0.5) + 1):
		if N % i == 0:
			N -= i
			c += 1
			f = 0
			break
	if f:
		N = 0
		c = 1
print(c + N // 2)


import math
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	i = 3
	f = 0
	c = 0
	while i <= int(math.ceil(math.sqrt(n))):
		if n % i == 0:
			c += 1
			n = n - i
			if n % 2 == 0:
				f = 1
				print(c + n // 2)
				break
			else:
				i = 3
		else:
			i += 1
	if f == 0:
		print(c + 1)


def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	x = smallestDivisor(n)
	ans = 1
	n = n - x
	ans = ans + n // 2
	print(ans)


import sys
primes = list(range(1, 141423))
for p in primes[1:]:
	for b in range(p + p, 141423, p):
		primes[b - 1] = -1
primes = list(filter(lambda x: not x == -1, primes))[1:]
n = int(input())
for p in primes:
	if n % p == 0:
		print(int((n - p) / 2 + 1))
		sys.exit()
print(1)


def smallest(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
n = int(input())
if smallest(n) == n:
	print(1)
	exit()
print((n - smallest(n)) // 2 + 1)


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
from math import sqrt
n = II()
isPrime = True
for i in range(2, int(sqrt(n)) + 1):
	if n % i == 0:
		isPrime = False
		break
if isPrime:
	i = n
print(1 + (n - i) // 2)


c = int(input())
i = 2
while i * i <= c:
	if c % i == 0:
		break
	else:
		i += 1
else:
	i = c
print(1 + (c - i) // 2)


import math

def get_least_prime_div(a):
	for div in range(2, int(math.sqrt(a)) + 2):
		if a % div == 0:
			return div
	return a
a = int(input())
total_steps = 0
if a % 2 == 0:
	total_steps += a // 2
	a = 0
if a % 2 != 0:
	div = get_least_prime_div(a)
	total_steps = 1
	a -= div
	total_steps += a // 2
	a = 0
print(total_steps)


n = int(input())
new_n = n
if n % 2 == 0:
	print(n // 2)
else:
	i = 3
	count = 0
	while i * i <= n:
		if n % i == 0:
			new_n = n - i
			break
		i += 1
	if new_n == 0 or new_n == n:
		print(1)
	else:
		print(new_n // 2 + 1)


n = int(input())
prost = 0
if n % 2 == 0:
	n //= 2
	print(n)
	exit(0)
else:
	f = int(1)
	i = int(3)
	while i * i <= n:
		if n % i == 0:
			prost = i
			f = 0
			break
		i += 1
	if f == 1:
		prost = n
	n -= prost
	n //= 2
	n += 1
	print(n)


n = int(input())
count = 0
while n != 0:
	if n % 2 == 0:
		count += n // 2
		break
	flag = 0
	for i in range(2, int(n ** 0.5 + 100)):
		if n % i == 0:
			flag = 1
			break
	count += 1
	if flag == 0:
		break
	else:
		n -= i
print(count)


n = int(input())
f = True
for i in range(2, int(n ** 0.5) + 1):
	if n % i == 0:
		m = i
		f = False
		break
if f:
	m = n
n -= m
c = 1 + n // 2
print(c)


from math import floor, sqrt
try:
	int
except NameError:
	long = int

def fac(n):
	step = lambda x: 1 + (x << 2) - (x >> 1 << 1)
	maxq = int(floor(sqrt(n)))
	d = 1
	q = n % 2 == 0 and 2 or 3
	while q <= maxq and n % q != 0:
		q = step(d)
		d += 1
	return q <= maxq and [q] + fac(n // q) or [n]

def _try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2 ** i * d, n) == n - 1:
			return False
	return True

def is_prime(n, _precision_for_huge_n=16):
	if n in _known_primes or n in (0, 1):
		return True
	if any((n % p == 0 for p in _known_primes)):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	if n < 1373653:
		return not any((_try_composite(a, d, n, s) for a in (2, 3)))
	if n < 25326001:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5)))
	if n < 118670087467:
		if n == 3215031751:
			return False
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7)))
	if n < 2152302898747:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11)))
	if n < 3474749660383:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13)))
	if n < 341550071728321:
		return not any((_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17)))
	return not any((_try_composite(a, d, n, s) for a in _known_primes[:_precision_for_huge_n]))
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]
n = int(input())
x = fac(n)[0]
if is_prime(n):
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	print((n - x) // 2 + 1)


n = int(input())

def prime(n):
	for i in range(3, int(n ** (1 / 2)) + 1, 2):
		if n % i == 0:
			return i
	return 1
if n % 2 == 0:
	print(n // 2)
elif prime(n) == 1:
	print(1)
else:
	print(1 + (n - prime(n)) // 2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
divisors = []

def Sieve():
	mark = set()
	i = 2
	while i * i <= 100009:
		if i not in mark:
			p = i * i
			while p <= 100009:
				mark.add(p)
				p = p + i
		i += 1
	i = 2
	while i <= 100009:
		if i not in mark:
			divisors.append(i)
		i += 1
n = int(input())
Sieve()
check = False
res = 0
for divisor in divisors:
	if n % divisor == 0:
		res += 1
		n = n - divisor
		check = True
		break
if check == False:
	print(1)
else:
	res = res + int(n / 2)
	print(res)


from collections import deque as de
import math

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors
n = int(input())
if isPrime(n):
	print(1)
elif n % 2:
	l = get_prime_factors(n)
	print((n - l[0]) // 2 + 1)
else:
	print(n // 2)


def prime_factors(n):
	i = 2
	f = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			f.append(i)
	if n > 1:
		f.append(n)
	return f

def solve(n):
	if n < 2:
		return 0
	f = prime_factors(n)
	if f[0] == 2:
		return n // f[0]
	else:
		return 1 + solve(n - f[0])

def main():
	n = int(input())
	print(solve(n))
main()


n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	x = 3
	achou = False
	while not achou and x * x <= n:
		if n % x == 0:
			achou = True
		else:
			x += 2
	if achou:
		print((n - x) // 2 + 1)
	else:
		print(1)


n = input()
n = int(n)
ans = 0
for i in range(2, 1000001):
	if n % i == 0:
		print(1 + (n - i) // 2)
		exit()
print(1)


import sys
import math
f = sys.stdin
n = int(f.readline().rstrip())
if n % 2 == 0:
	print(n // 2)
else:
	count = 0
	temp = 0
	sq = int(math.sqrt(n))
	if sq >= 3:
		for i in range(3, sq + 1, 2):
			if n % i == 0:
				n = n - i
				count += 1
				i = 3
				if n % 2 == 0:
					print(n // 2 + count)
					temp = 1
					break
	if temp == 0:
		print(1)


import math, sys

def smallest(n):
	while n % 2 == 0:
		return 2
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			return i
			n = n / i
	if n > 2:
		return n
ans = 0
n = int(input())
if n % 2 == 0:
	print(n // 2)
	sys.exit()
while n > 0:
	xx = smallest(n)
	n = n - xx
	if n % 2 == 0:
		ans += 1
		print(ans + n // 2)
		sys.exit()
	ans += 1
print(ans)


def fun(n):
	for _ in range(2, int(pow(n, 1 / 2)) + 1):
		if n % _ == 0:
			return _
	return n
n = int(input())
print((n - fun(n)) // 2 + 1)


import math

def factors(k):
	L = []
	for i in range(2, int(math.sqrt(k)) + 1):
		if k % i == 0:
			if i == k // i:
				L.append(i)
			else:
				L.append(i)
				L.append(k // i)
	L.append(k)
	return L

def prime(p):
	for i in range(2, int(math.sqrt(p)) + 1):
		if p % i == 0:
			return 0
	return 1
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	a = factors(n)
	for i in a:
		if prime(i):
			print((n - i) // 2 + 1)
			break


def fun(n):
	if n % 2 == 0:
		return n // 2
	else:
		for p in range(2, int(n ** 0.5) + 1):
			if n % p == 0:
				return 1 + (n - p) // 2
		return 1
print(fun(int(input())))


try:

	def pr(n):
		if n <= 1:
			return False
		if n <= 3:
			return True
		if n % 2 == 0 or n % 3 == 0:
			return False
		i = 5
		while i * i <= n:
			if n % i == 0 or n % (i + 2) == 0:
				return False
			i = i + 6
		return True
	import math
	m = int(input())
	if pr(m) == True:
		print(1)
	elif m % 2 == 0:
		print(m // 2)
	else:
		p = int(math.sqrt(m) + 1)
		for i in range(2, p):
			if pr(i) == True and m % i == 0:
				k = i
				break
		m = m - k
		l = m // 2
		print(l + 1)
except:
	pass


def find(N):
	P = N
	for i in range(2, int(N ** 0.5) + 1):
		if N % i == 0:
			P = i
			break
	if P % 2 == 1:
		N -= P
		ans = 1
		ans += N // 2
		return ans
	else:
		return N // 2
	ans = N // P
	return ans
N = int(input())
print(find(N))


def prime(v):
	index = 2
	while index * index <= v:
		if v % index == 0:
			return index
		index += 1
	return v
n = int(input())
print(1 + (n - prime(n)) // 2)


import math as m

def nextPrime(x):
	ans = x
	size = int(m.sqrt(x))
	for j in range(2, size + 1):
		if x % j == 0:
			ans = j
			break
	return ans

def run():
	n = int(input())
	p = nextPrime(n)
	ans = (n - p) // 2 + 1
	print(ans)
run()


N = int(input())
res = False
i = 2
while i * i <= N:
	if N % i == 0:
		count = int(1 + (N - i) / 2)
		print(count)
		res = True
		break
	i += 1
if not res:
	print('1')


n = int(input())
p = 0
k = 2
while k * k <= n:
	if n % k == 0:
		p = -1
		break
	else:
		k += 1
if p == 0:
	print(1)
else:
	print((n - k) // 2 + 1)


import math
n = int(input())
count = 0
while True:
	if n == 0:
		break
	if n % 2 == 0:
		count += n // 2
		break
	i = 2
	d = n
	while i < int(math.sqrt(n)) + 1:
		if n % i == 0:
			d = i
			break
		i += 1
	n -= d
	count += 1
print(count)


from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)

class Operation:

	def __init__(self, name, function, function_on_equal, neutral_value=0):
		self.name = name
		self.f = function
		self.f_on_equal = function_on_equal

def add_multiple(x, count):
	return x * count

def min_multiple(x, count):
	return x

def max_multiple(x, count):
	return x
sum_operation = Operation('sum', sum, add_multiple, 0)
min_operation = Operation('min', min, min_multiple, 1000000000.0)
max_operation = Operation('max', max, max_multiple, -1000000000.0)

class SegmentTree:

	def __init__(self, array, operations=[sum_operation, min_operation, max_operation]):
		self.array = array
		if type(operations) != list:
			raise TypeError('operations must be a list')
		self.operations = {}
		for op in operations:
			self.operations[op.name] = op
		self.root = SegmentTreeNode(0, len(array) - 1, self)

	def query(self, start, end, operation_name):
		if self.operations.get(operation_name) == None:
			raise Exception('This operation is not available')
		return self.root._query(start, end, self.operations[operation_name])

	def summary(self):
		return self.root.values

	def update(self, position, value):
		self.root._update(position, value)

	def update_range(self, start, end, value):
		self.root._update_range(start, end, value)

	def __repr__(self):
		return self.root.__repr__()

class SegmentTreeNode:

	def __init__(self, start, end, segment_tree):
		self.range = (start, end)
		self.parent_tree = segment_tree
		self.range_value = None
		self.values = {}
		self.left = None
		self.right = None
		if start == end:
			self._sync()
			return
		self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
		self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
		self._sync()

	def _query(self, start, end, operation):
		if end < self.range[0] or start > self.range[1]:
			return None
		if start <= self.range[0] and self.range[1] <= end:
			return self.values[operation.name]
		self._push()
		left_res = self.left._query(start, end, operation) if self.left else None
		right_res = self.right._query(start, end, operation) if self.right else None
		if left_res is None:
			return right_res
		if right_res is None:
			return left_res
		return operation.f([left_res, right_res])

	def _update(self, position, value):
		if position < self.range[0] or position > self.range[1]:
			return
		if position == self.range[0] and self.range[1] == position:
			self.parent_tree.array[position] = value
			self._sync()
			return
		self._push()
		self.left._update(position, value)
		self.right._update(position, value)
		self._sync()

	def _update_range(self, start, end, value):
		if end < self.range[0] or start > self.range[1]:
			return
		if start <= self.range[0] and self.range[1] <= end:
			self.range_value = value
			self._sync()
			return
		self._push()
		self.left._update_range(start, end, value)
		self.right._update_range(start, end, value)
		self._sync()

	def _sync(self):
		if self.range[0] == self.range[1]:
			for op in self.parent_tree.operations.values():
				current_value = self.parent_tree.array[self.range[0]]
				if self.range_value is not None:
					current_value = self.range_value
				self.values[op.name] = op.f([current_value])
		else:
			for op in self.parent_tree.operations.values():
				result = op.f([self.left.values[op.name], self.right.values[op.name]])
				if self.range_value is not None:
					bound_length = self.range[1] - self.range[0] + 1
					result = op.f_on_equal(self.range_value, bound_length)
				self.values[op.name] = result

	def _push(self):
		if self.range_value is None:
			return
		if self.left:
			self.left.range_value = self.range_value
			self.right.range_value = self.range_value
			self.left._sync()
			self.right._sync()
			self.range_value = None

	def __repr__(self):
		ans = '({}, {}): {}\n'.format(self.range[0], self.range[1], self.values)
		if self.left:
			ans += self.left.__repr__()
		if self.right:
			ans += self.right.__repr__()
		return ans

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def test_print(*args):
	if test:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result
TestCases = False
test = False

def main():
	n = get_int()
	fac = primeFactors(n)
	if len(fac.keys()) == 0:
		print(1)
	else:
		print((n - min(fac.keys())) // 2 + 1)
if TestCases:
	for _ in range(get_int()):
		cProfile.run('main()') if test else main()
else:
	cProfile.run('main()') if test else main()


from math import sqrt

def divisors(num):
	for i in range(2, int(sqrt(num)) + 1):
		if num % i == 0:
			return i
	return num

def resulting(n):
	count = 0
	if n % 2 != 0:
		n -= divisors(n)
		count += 1
	return count + n // 2
print(resulting(int(input())))


import math
n = int(input())
countOfSubtractions = 0
iteraction = 0
even = [0, 2, 4, 6, 8]
while n > 0:
	subtract = 0
	iteraction += 1
	lastChar = int(str(n)[-1])
	if lastChar in even:
		countOfSubtractions += int(n / 2) - 1
		n = -1
	elif lastChar == '3':
		subtract = 3
	elif sum([int(x) for x in str(n)]) == 3:
		subtract = 3
	elif lastChar == '5':
		subtract = 5
	elif n % 7 == 0:
		subtract = 7
	else:
		i = 3
		while math.pow(i, 2) <= n:
			if n % i == 0:
				subtract = i
				break
			i += 2
		if subtract == 0:
			subtract = n
	n -= subtract
	countOfSubtractions += 1
print(countOfSubtractions)


n = int(input())
from math import sqrt
4
if n % 2 == 0:
	print(int(n / 2))
else:
	bank = 0
	for i in range(3, int(sqrt(n)) + 1):
		if n % i == 0:
			bank = i
			break
	if bank == 0:
		bank = n
	print((n - bank) // 2 + 1)


import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

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

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def revn(n):
	m = 0
	while n > 0:
		m = m * 10 + n % 10
		n = n // 10
	return m
n = ii()
if prime(n):
	print(1)
elif n % 2 == 0:
	print(n // 2)
else:
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			print(1 + (n - d) // 2)
			exit()


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
n = read_int()
i = 2
while i * i < n and n % i:
	i += 1
if i * i <= n:
	print((n - i) // 2 + 1)
else:
	print(1)


def is_prime(n):
	sqrt = int(n ** 0.5)
	divisors = 0
	for i in range(1, sqrt + 1):
		if n % i == 0:
			divisors += 1
		if divisors > 1:
			return False
	return True
n = int(input())
i = 1
if is_prime(n):
	print(1)
else:
	while i <= n:
		i += 1
		if n % i == 0 and is_prime(i):
			n -= i
			break
	if n % 2 == 0:
		print(n // 2 + 1)
	else:
		print(n // i + 1)


n = eval(input())
if n % 2 == 0:
	print(n // 2)
	exit(0)
k = int(n ** 0.5)
flag = True
for i in range(2, k + 1):
	if n % i == 0:
		flag = False
		break
if flag:
	print(1)
else:
	n = n - i
	print(n // 2 + 1)


def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if not n % i:
			return False
	return True
n = int(input())
c = 0
while True:
	if n % 2 == 0:
		c += n // 2
		break
	if is_prime(n):
		c += 1
		break
	for i in range(2, n):
		if is_prime(i) and n % i == 0:
			break
	n -= i
	c += 1
	if n == 0:
		break
print(c)


n = int(input())

def func(n):
	if n % 2 == 0:
		return n // 2
	index = 2
	check = False
	while index * index <= n:
		if n % index == 0:
			check = True
			return 1 + func(n - index)
		index += 1
	if check == False:
		return 1
print(func(n))


import math

def div(n):
	ans = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans = i
			break
	if ans > 0:
		return ans
	else:
		return n
n = int(input())
if n % 2 == 0:
	print(n // 2)
else:
	a = div(n)
	n = n - a
	print(1 + n // 2)


from sys import stdin

def main():
	n = int(input())
	ans = 0
	if n % 2 == 1:
		ans = 1
		d = 3
		while d * d <= n and n % d != 0:
			d += 2
		if d * d > n:
			d = n
		n = n - d
	ans += n // 2
	print(ans)
	return
main()


import sys
from collections import defaultdict
import math
n = int(sys.stdin.readline())

def getfactors(num):
	ans = 0
	if num % 2 == 0:
		return num // 2
	fac = -1
	for i in range(2, int(math.sqrt(num)) + 1):
		if num % i == 0:
			fac = i
			break
	if fac != -1:
		num -= fac
		ans = 1
		ans += num // 2
		return ans
	return 1
ans = getfactors(n)
print(ans)


n = int(input())
if n % 2 == 0:
	resp = n // 2
else:
	primos = []
	numeros = [False, False] + [True] * 99999
	raiz = 100001 ** 0.5 + 2
	for i in range(2, 100001):
		if numeros[i]:
			if i <= raiz:
				for j in range(i * i, 100001, i):
					numeros[j] = False
			primos.append(i)
	resp = 0
	while n % 2 != 0:
		if n <= 100001 and numeros[n]:
			break
		i = 0
		while i < len(primos) and n % primos[i] != 0:
			i += 1
		if i == len(primos):
			break
		resp += 1
		n -= primos[i]
	if n % 2 == 0:
		resp += n // 2
	else:
		resp += 1
print(resp)