IT City company developing computer games decided to upgrade its way to reward its employees. Now it looks the following way. After a new game release users start buying it actively, and the company tracks the number of sales with precision to each transaction. Every time when the next number of sales is not divisible by any number from 2 to 10 every developer of this game gets a small bonus.

A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.


-----Input-----

The only line of the input contains one integer n (1 ≤ n ≤ 10^18) — the prediction on the number of people who will buy the game.


-----Output-----

Output one integer showing how many numbers from 1 to n are not divisible by any number from 2 to 10.


-----Examples-----
Input
12

Output
2

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
n = int(input())
res = n // 2 + n // 3 + n // 5 + n // 7 - n // 6 - n // 10 - n // 14 - n // 15 - n // 21 - n // 35 + (n // 30 + n // 42 + n // 70 + n // 105) - n // 210
print(n - res)


n = int(input())
p = [2, 3, 5, 7, 30, 42, 70, 105]
np = [6, 10, 14, 15, 21, 35, 210]
ans = 0
for i in p:
	ans += n // i
for i in np:
	ans -= n // i
print(n - ans)


import os, sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
from math import gcd
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
t = n
ans = n
for i in [2, 3, 5, 7]:
	ans -= n // i
for i in [6, 10, 14, 15, 21, 35]:
	ans += n // i
for i in [2 * 3 * 5, 2 * 3 * 7, 2 * 5 * 7, 3 * 5 * 7]:
	ans -= n // i
ans += n // (2 * 3 * 5 * 7)
print(ans)


import sys
from math import gcd

def read():
	return sys.stdin.readline().strip()

def printf(a, sep=' ', end='\n'):
	sys.stdout.write(sep.join(map(str, a)) + end)

def readf():
	return [int(i) for i in read().split()]

def main():
	n = int(read())
	ans = n
	p = [2, 3, 5, 7]
	ans -= n // 2 + n // 3 + n // 5 + n // 7
	ans += n // 6 + n // 10 + n // 14 + n // 21 + n // 15 + n // 35
	ans -= n // 30 + n // 42 + n // 105 + n // 70
	ans += n // 210
	printf([ans])
main()


def write(n):
	print(0, 2, 3, 5, 7, 6, 10, 14, 15, 21, 35)
	print(n, n // 2, n // 3, n // 5, n // 7, n // 6, n // 10, n // 14, n // 15, n // 21, n // 35)
n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // (2 * 3 * 5) - n // (2 * 3 * 7) - n // (2 * 5 * 7) - n // (3 * 5 * 7) + n // (2 * 3 * 5 * 7))


theset = [2, 3, 5, 7]

def brute(cur, i, n):
	res = 0
	if i < len(theset):
		res += brute(cur, i + 1, n)
		cur.append(theset[i])
		res += brute(cur, i + 1, n)
		cur.pop()
	else:
		k = 1
		for elem in cur:
			k *= elem
		res += (+1 if len(cur) % 2 == 0 else -1) * (n // k)
	return res
n = int(input())
print(brute([], 0, n))


n = int(input())
p = n - n // 2 - n // 3 - n // 5 - n // 7
c2 = n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35
c3 = n // 30 + n // 42 + n // 70 + n // 105
c4 = n // (2 * 3 * 5 * 7)
p = p + c2 - c3 + c4
print(p)


n = int(input())
t = [False] * 2521
sum = 0
for a in range(2521):
	t[a] = a % 2 == 0 or a % 3 == 0 or a % 4 == 0 or (a % 5 == 0) or (a % 6 == 0) or (a % 7 == 0) or (a % 8 == 0) or (a % 9 == 0) or (a % 10 == 0)
	if not t[a]:
		sum += 1
ret = sum * (n // 2520)
for a in range(n % 2520 + 1):
	ret += not t[a]
print(ret)


n = 0

def add(x, y):
	m = int(pow(-1, x))
	return m * (n // y)
n = int(input())
a = n
a += add(1, 2)
a += add(1, 3)
a += add(1, 5)
a += add(1, 7)
a += add(0, 2 * 3)
a += add(0, 2 * 5)
a += add(0, 2 * 7)
a += add(0, 3 * 5)
a += add(0, 3 * 7)
a += add(0, 5 * 7)
a += add(1, 2 * 3 * 5)
a += add(1, 2 * 3 * 7)
a += add(1, 2 * 5 * 7)
a += add(1, 3 * 5 * 7)
a += add(0, 2 * 3 * 5 * 7)
print(a)


import sys
input = sys.stdin.buffer.readline
n = int(input())
divisable = n // 2 + n // 3 + n // 5 + n // 7 - n // 6 - n // 10 - n // 14 - n // 15 - n // 21 - n // 35 + n // 30 + n // 42 + n // 70 + n // 105 - n // 210
print(n - divisable)


import math
n = int(input())
a = n // 2 + n // 3 + n // 5 + n // 7
b = n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35
c = n // 30 + n // 42 + n // 70 + n // 105
d = n // 210
print(n - a + b - c + d)


n = int(input())

def Solution(n):
	return n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // 30 - n // 42 - n // 70 - n // 105 + n // 210
print(Solution(n))


import os, sys, pdb
import time, calendar, datetime
import math, itertools
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
l = []
for i in range(2520):
	div = 1
	for j in range(2, 11):
		if i % j == 0:
			div = 0
	l.append(div)
(n,) = list(map(int, input().split()))
ans = n // 2520 * sum(l) + sum(l[:n % 2520 + 1])
print(ans)


n = int(input())
res = n
res -= n // 2
res -= n // 3
res -= n // 5
res -= n // 7
res += n // 6
res += n // 10
res += n // 14
res += n // 15
res += n // 21
res += n // 35
res -= n // (3 * 5 * 7)
res -= n // (2 * 5 * 7)
res -= n // (2 * 3 * 7)
res -= n // (2 * 3 * 5)
res += n // (2 * 3 * 5 * 7)
print(res)


n = int(input())
y = n // 2
y += n // 3
y += n // 5
y += n // 7
y -= n // 6
y -= n // 15
y -= n // 35
y -= n // 14
y -= n // 21
y -= n // 10
y += n * 2 // 210
y += n * 3 // 210
y += n * 5 // 210
y += n * 7 // 210
y -= n // 210
print(n - y)


incl = [2, 3, 5, 7, 30, 42, 70, 105]
excl = [6, 10, 14, 15, 21, 35, 210]
n = int(input())
answ = 0
for k in incl:
	answ += n // k
for k in excl:
	answ -= n // k
print(n - answ)


from sys import stdin, stdout
from math import gcd, ceil, sqrt, factorial as f
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
n = ii1()
div = [2, 3, 5, 7, 30, 42, 70, 105]
res = n
for i in div:
	res -= n // i
div1 = [6, 10, 14, 15, 21, 35, 210]
for i in div1:
	res += n // i
print(res)


M = 2 * 3 * 5 * 7
v = [0] * M
for i in range(1, M):
	v[i] = v[i - 1] + bool(i % 2 and i % 3 and i % 5 and i % 7)
n = int(input())
print(n // M * v[-1] + v[n % M])


import sys
from collections import Counter

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

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

def input():
	return sys.stdin.readline().strip('\n')
n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // 30 - n // 42 - n // 70 - n // 105 + n // 210)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from math import sqrt, floor, factorial, gcd, log
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations
from math import gcd
from bisect import bisect
input = lambda : sys.stdin.readline().rstrip('\r\n')
read = lambda : list(map(int, input().strip().split(' ')))

def mul(arr):
	ans = 1
	for i in arr:
		ans *= i
	return ans

def solve():
	n = int(input())
	t = n
	primes = [2, 3, 5, 7]
	for i in range(1, 4):
		for j in combinations(primes, i):
			if i % 2:
				n -= t // mul(list(j))
			else:
				n += t // mul(list(j))
	n += t // mul(primes)
	print(n)
solve()


n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7) - n // (2 * 3 * 5) - n // (2 * 3 * 7) - n // (2 * 5 * 7) - n // (3 * 5 * 7) + n // (2 * 3 * 5 * 7))


def main():
	n = int(input())
	one = n // 2 + n // 3 + n // 5 + n // 7
	two = n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7)
	three = n // (2 * 3 * 5) + n // (2 * 3 * 7) + n // (2 * 5 * 7) + n // (3 * 5 * 7)
	four = n // (2 * 3 * 5 * 7)
	print(n - one + two - three + four)
main()


from sys import stdin
n = int(stdin.readline())
d2 = n // 2
d3 = n // 3
d5 = n // 5
d7 = n // 7
d23 = n // (2 * 3)
d25 = n // (2 * 5)
d27 = n // (2 * 7)
d35 = n // (3 * 5)
d37 = n // (3 * 7)
d57 = n // (5 * 7)
d235 = n // (2 * 3 * 5)
d237 = n // (2 * 3 * 7)
d257 = n // (2 * 5 * 7)
d357 = n // (3 * 5 * 7)
d2357 = n // (2 * 3 * 5 * 7)
ans = d2 + d3 + d5 + d7 - (d23 + d25 + d27 + d35 + d37 + d57) + (d235 + d237 + d257 + d357) - d2357
print(n - ans)


import math
from math import *
n = int(input())
d = [2, 3, 5, 7]
ans = n
for i in range(4):
	ans -= n // d[i]
for i in range(4):
	for j in range(i + 1, 4):
		ans += n // (d[i] * d[j])
for i in range(4):
	for j in range(i + 1, 4):
		for k in range(j + 1, 4):
			ans -= n // (d[i] * d[j] * d[k])
ans += n // (2 * 3 * 5 * 7)
print(ans)


n = int(input())
counter = 0
for i in range(0, 2520):
	if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0) and (i % 7 != 0):
		counter += 1
count = counter * (n // 2520)
for i in range(1, n % 2520 + 1):
	if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0) and (i % 7 != 0):
		count += 1
print(count)


n = int(input())
x = 0
x += n // 2520 * 576
for i in range(1, n % 2520 + 1):
	d = True
	for j in range(2, 11):
		if i % j == 0:
			d = False
			break
	if d:
		x += 1
print(x)


a = int(input())
b = a - a // 2 - a // 3 - a // 5 - a // 7 + a // 6 + a // 10 + a // 14 + a // 15 + a // 21 + a // 35 - a // 30 - a // 42 - a // 70 - a // 105 + a // 210
print(b)


import math
n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + 0 + n // 6 + n // 10 + n // 15 + n // 14 + n // 21 - n // 30 - n // 105 + n // 35 - n // 70 + n // 210 - n // 42)


n = int(input())
ost = n // 2520
ans = 0
for i in range(1, n % 2520 + 1):
	if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or (i % 7 == 0):
		ans += 1
print(ost * 576 + n % 2520 - ans)


w = int(input())
total = w - w // 2 - w // 3 - w // 5 - w // 7 + w // 6 + w // 10 + w // 14 + w // 15 + w // 21 + w // 35 - w // 30 - w // 42 - w // 70 - w // 105 + w // 210
print(total)


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

def solver(n):
	factors = [2, 3, 5, 7]
	singles = n // 2 + n // 3 + n // 5 + n // 7
	pairs = n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7)
	triples = n // (2 * 3 * 5) + n // (2 * 3 * 7) + n // (2 * 5 * 7) + n // (3 * 5 * 7)
	quads = n // (2 * 3 * 5 * 7)
	return n - singles + pairs - triples + quads
main()


import itertools
import math
p = int(input())
aa = p
for i in range(1, 11):
	t = list(itertools.combinations([2, 3, 5, 7], i))
	for j in t:
		ans = 1
		for k in j:
			ans *= k
		ans = p // ans
		if i & 1:
			aa -= ans
		else:
			aa += ans
print(aa)


s = [2, 3, 5, 7]
n = int(input())
ans = 0
for i in s:
	ans += n // i
for i in range(len(s)):
	for j in range(i + 1, len(s)):
		ans -= n // (s[i] * s[j])
for i in range(len(s)):
	for j in range(i + 1, len(s)):
		for k in range(j + 1, len(s)):
			ans += n // (s[i] * s[j] * s[k])
ans -= n // (2 * 3 * 5 * 7)
print(n - ans)


n = int(input())
a = [2, 3, 5, 7]
ans = 0
import operator
import itertools
import functools
for i in range(1, 5):
	for p in itertools.combinations(a, i):
		x = functools.reduce(operator.mul, p)
		ans += (-1) ** (i + 1) * (n // x)
print(n - ans)


def main():
	(res, n) = divmod(int(input()) + 1, 2520)
	l = [1] * n
	for p in range(2, 11):
		for i in range(0, n, p):
			l[i] = 0
	print(res * 576 + sum(l))
main()


from itertools import combinations, accumulate, groupby, count
from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from os import *
from re import *

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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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:
			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')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (fast, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end='\n'):
	stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
n = int(z())
s = 0
for i in range(2520):
	ans = True
	if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or (i % 7 == 0):
		ans = False
	if ans and i <= n:
		s += (n - i) // 2520
		s += 1
print(s)


n = int(input())
a = n // 2 + n // 3 + n // 5 + n // 7
b = n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7)
c = n // (2 * 3 * 5) + n // (2 * 3 * 7) + n // (3 * 5 * 7) + n // (2 * 5 * 7)
d = n // (2 * 3 * 5 * 7)
print(n - a + b - c + d)


x = int(input())
y = x // 210 * 48
for i in range(1, x % 210 + 1):
	if i % 2 and i % 3 and i % 5 and i % 7:
		y += 1
print(y)


n = int(input())
m = n // 210 * 48
for j in range(210 * (n // 210) + 1, n + 1):
	if j % 2 != 0 and j % 3 != 0 and (j % 7 != 0) and (j % 5 != 0):
		m += 1
print(m)


n = int(input())
neg = [2, 3, 5, 7, 2 * 3 * 5, 2 * 3 * 7, 2 * 5 * 7, 3 * 5 * 7]
pos = [1, 2 * 3, 2 * 5, 2 * 7, 3 * 5, 3 * 7, 5 * 7, 2 * 3 * 5 * 7]
ret = 0
for x in neg:
	ret -= n // x
for x in pos:
	ret += n // x
print(ret)


from math import *
n = int(input())
T = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 33, 33, 34, 34, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 41, 41, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 45, 45, 45, 45, 46, 46, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50, 50, 51, 51, 51, 51, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 55, 55, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 62, 62, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 65, 65, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 72, 72, 72, 72, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 79, 79, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 82, 82, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 87, 87, 87, 87, 88, 88, 88, 88, 88, 88, 89, 89, 90, 90, 90, 90, 90, 90, 91, 91, 91, 91, 92, 92, 93, 93, 93, 93, 94, 94, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 96, 96, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 98, 98, 99, 99, 99, 99, 100, 100, 101, 101, 101, 101, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 104, 104, 104, 104, 105, 105, 105, 105, 106, 106, 107, 107, 107, 107, 108, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 110, 110, 111, 111, 111, 111, 111, 111, 112, 112, 112, 112, 113, 113, 114, 114, 114, 114, 114, 114, 115, 115, 115, 115, 116, 116, 116, 116, 116, 116, 117, 117, 117, 117, 117, 117, 117, 117, 118, 118, 118, 118, 119, 119, 120, 120, 120, 120, 121, 121, 122, 122, 122, 122, 123, 123, 123, 123, 123, 123, 123, 123, 124, 124, 124, 124, 124, 124, 125, 125, 125, 125, 126, 126, 126, 126, 126, 126, 127, 127, 128, 128, 128, 128, 129, 129, 129, 129, 129, 129, 130, 130, 131, 131, 131, 131, 131, 131, 132, 132, 132, 132, 132, 132, 133, 133, 133, 133, 134, 134, 135, 135, 135, 135, 136, 136, 136, 136, 136, 136, 137, 137, 138, 138, 138, 138, 138, 138, 139, 139, 139, 139, 140, 140, 141, 141, 141, 141, 142, 142, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 144, 144, 145, 145, 145, 145, 145, 145, 145, 145, 145, 145, 146, 146, 147, 147, 147, 147, 148, 148, 149, 149, 149, 149, 150, 150, 150, 150, 150, 150, 151, 151, 152, 152, 152, 152, 152, 152, 153, 153, 153, 153, 154, 154, 155, 155, 155, 155, 156, 156, 156, 156, 156, 156, 157, 157, 157, 157, 157, 157, 158, 158, 159, 159, 159, 159, 159, 159, 160, 160, 160, 160, 161, 161, 162, 162, 162, 162, 162, 162, 163, 163, 163, 163, 164, 164, 164, 164, 164, 164, 165, 165, 165, 165, 165, 165, 165, 165, 166, 166, 166, 166, 167, 167, 168, 168, 168, 168, 169, 169, 170, 170, 170, 170, 171, 171, 171, 171, 171, 171, 171, 171, 172, 172, 172, 172, 172, 172, 173, 173, 173, 173, 174, 174, 174, 174, 174, 174, 175, 175, 176, 176, 176, 176, 177, 177, 177, 177, 177, 177, 178, 178, 179, 179, 179, 179, 179, 179, 180, 180, 180, 180, 180, 180, 181, 181, 181, 181, 182, 182, 183, 183, 183, 183, 184, 184, 184, 184, 184, 184, 185, 185, 186, 186, 186, 186, 186, 186, 187, 187, 187, 187, 188, 188, 189, 189, 189, 189, 190, 190, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 192, 192, 193, 193, 193, 193, 193, 193, 193, 193, 193, 193, 194, 194, 195, 195, 195, 195, 196, 196, 197, 197, 197, 197, 198, 198, 198, 198, 198, 198, 199, 199, 200, 200, 200, 200, 200, 200, 201, 201, 201, 201, 202, 202, 203, 203, 203, 203, 204, 204, 204, 204, 204, 204, 205, 205, 205, 205, 205, 205, 206, 206, 207, 207, 207, 207, 207, 207, 208, 208, 208, 208, 209, 209, 210, 210, 210, 210, 210, 210, 211, 211, 211, 211, 212, 212, 212, 212, 212, 212, 213, 213, 213, 213, 213, 213, 213, 213, 214, 214, 214, 214, 215, 215, 216, 216, 216, 216, 217, 217, 218, 218, 218, 218, 219, 219, 219, 219, 219, 219, 219, 219, 220, 220, 220, 220, 220, 220, 221, 221, 221, 221, 222, 222, 222, 222, 222, 222, 223, 223, 224, 224, 224, 224, 225, 225, 225, 225, 225, 225, 226, 226, 227, 227, 227, 227, 227, 227, 228, 228, 228, 228, 228, 228, 229, 229, 229, 229, 230, 230, 231, 231, 231, 231, 232, 232, 232, 232, 232, 232, 233, 233, 234, 234, 234, 234, 234, 234, 235, 235, 235, 235, 236, 236, 237, 237, 237, 237, 238, 238, 239, 239, 239, 239, 239, 239, 239, 239, 239, 239, 240, 240, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 242, 242, 243, 243, 243, 243, 244, 244, 245, 245, 245, 245, 246, 246, 246, 246, 246, 246, 247, 247, 248, 248, 248, 248, 248, 248, 249, 249, 249, 249, 250, 250, 251, 251, 251, 251, 252, 252, 252, 252, 252, 252, 253, 253, 253, 253, 253, 253, 254, 254, 255, 255, 255, 255, 255, 255, 256, 256, 256, 256, 257, 257, 258, 258, 258, 258, 258, 258, 259, 259, 259, 259, 260, 260, 260, 260, 260, 260, 261, 261, 261, 261, 261, 261, 261, 261, 262, 262, 262, 262, 263, 263, 264, 264, 264, 264, 265, 265, 266, 266, 266, 266, 267, 267, 267, 267, 267, 267, 267, 267, 268, 268, 268, 268, 268, 268, 269, 269, 269, 269, 270, 270, 270, 270, 270, 270, 271, 271, 272, 272, 272, 272, 273, 273, 273, 273, 273, 273, 274, 274, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 277, 277, 277, 277, 278, 278, 279, 279, 279, 279, 280, 280, 280, 280, 280, 280, 281, 281, 282, 282, 282, 282, 282, 282, 283, 283, 283, 283, 284, 284, 285, 285, 285, 285, 286, 286, 287, 287, 287, 287, 287, 287, 287, 287, 287, 287, 288, 288, 289, 289, 289, 289, 289, 289, 289, 289, 289, 289, 290, 290, 291, 291, 291, 291, 292, 292, 293, 293, 293, 293, 294, 294, 294, 294, 294, 294, 295, 295, 296, 296, 296, 296, 296, 296, 297, 297, 297, 297, 298, 298, 299, 299, 299, 299, 300, 300, 300, 300, 300, 300, 301, 301, 301, 301, 301, 301, 302, 302, 303, 303, 303, 303, 303, 303, 304, 304, 304, 304, 305, 305, 306, 306, 306, 306, 306, 306, 307, 307, 307, 307, 308, 308, 308, 308, 308, 308, 309, 309, 309, 309, 309, 309, 309, 309, 310, 310, 310, 310, 311, 311, 312, 312, 312, 312, 313, 313, 314, 314, 314, 314, 315, 315, 315, 315, 315, 315, 315, 315, 316, 316, 316, 316, 316, 316, 317, 317, 317, 317, 318, 318, 318, 318, 318, 318, 319, 319, 320, 320, 320, 320, 321, 321, 321, 321, 321, 321, 322, 322, 323, 323, 323, 323, 323, 323, 324, 324, 324, 324, 324, 324, 325, 325, 325, 325, 326, 326, 327, 327, 327, 327, 328, 328, 328, 328, 328, 328, 329, 329, 330, 330, 330, 330, 330, 330, 331, 331, 331, 331, 332, 332, 333, 333, 333, 333, 334, 334, 335, 335, 335, 335, 335, 335, 335, 335, 335, 335, 336, 336, 337, 337, 337, 337, 337, 337, 337, 337, 337, 337, 338, 338, 339, 339, 339, 339, 340, 340, 341, 341, 341, 341, 342, 342, 342, 342, 342, 342, 343, 343, 344, 344, 344, 344, 344, 344, 345, 345, 345, 345, 346, 346, 347, 347, 347, 347, 348, 348, 348, 348, 348, 348, 349, 349, 349, 349, 349, 349, 350, 350, 351, 351, 351, 351, 351, 351, 352, 352, 352, 352, 353, 353, 354, 354, 354, 354, 354, 354, 355, 355, 355, 355, 356, 356, 356, 356, 356, 356, 357, 357, 357, 357, 357, 357, 357, 357, 358, 358, 358, 358, 359, 359, 360, 360, 360, 360, 361, 361, 362, 362, 362, 362, 363, 363, 363, 363, 363, 363, 363, 363, 364, 364, 364, 364, 364, 364, 365, 365, 365, 365, 366, 366, 366, 366, 366, 366, 367, 367, 368, 368, 368, 368, 369, 369, 369, 369, 369, 369, 370, 370, 371, 371, 371, 371, 371, 371, 372, 372, 372, 372, 372, 372, 373, 373, 373, 373, 374, 374, 375, 375, 375, 375, 376, 376, 376, 376, 376, 376, 377, 377, 378, 378, 378, 378, 378, 378, 379, 379, 379, 379, 380, 380, 381, 381, 381, 381, 382, 382, 383, 383, 383, 383, 383, 383, 383, 383, 383, 383, 384, 384, 385, 385, 385, 385, 385, 385, 385, 385, 385, 385, 386, 386, 387, 387, 387, 387, 388, 388, 389, 389, 389, 389, 390, 390, 390, 390, 390, 390, 391, 391, 392, 392, 392, 392, 392, 392, 393, 393, 393, 393, 394, 394, 395, 395, 395, 395, 396, 396, 396, 396, 396, 396, 397, 397, 397, 397, 397, 397, 398, 398, 399, 399, 399, 399, 399, 399, 400, 400, 400, 400, 401, 401, 402, 402, 402, 402, 402, 402, 403, 403, 403, 403, 404, 404, 404, 404, 404, 404, 405, 405, 405, 405, 405, 405, 405, 405, 406, 406, 406, 406, 407, 407, 408, 408, 408, 408, 409, 409, 410, 410, 410, 410, 411, 411, 411, 411, 411, 411, 411, 411, 412, 412, 412, 412, 412, 412, 413, 413, 413, 413, 414, 414, 414, 414, 414, 414, 415, 415, 416, 416, 416, 416, 417, 417, 417, 417, 417, 417, 418, 418, 419, 419, 419, 419, 419, 419, 420, 420, 420, 420, 420, 420, 421, 421, 421, 421, 422, 422, 423, 423, 423, 423, 424, 424, 424, 424, 424, 424, 425, 425, 426, 426, 426, 426, 426, 426, 427, 427, 427, 427, 428, 428, 429, 429, 429, 429, 430, 430, 431, 431, 431, 431, 431, 431, 431, 431, 431, 431, 432, 432, 433, 433, 433, 433, 433, 433, 433, 433, 433, 433, 434, 434, 435, 435, 435, 435, 436, 436, 437, 437, 437, 437, 438, 438, 438, 438, 438, 438, 439, 439, 440, 440, 440, 440, 440, 440, 441, 441, 441, 441, 442, 442, 443, 443, 443, 443, 444, 444, 444, 444, 444, 444, 445, 445, 445, 445, 445, 445, 446, 446, 447, 447, 447, 447, 447, 447, 448, 448, 448, 448, 449, 449, 450, 450, 450, 450, 450, 450, 451, 451, 451, 451, 452, 452, 452, 452, 452, 452, 453, 453, 453, 453, 453, 453, 453, 453, 454, 454, 454, 454, 455, 455, 456, 456, 456, 456, 457, 457, 458, 458, 458, 458, 459, 459, 459, 459, 459, 459, 459, 459, 460, 460, 460, 460, 460, 460, 461, 461, 461, 461, 462, 462, 462, 462, 462, 462, 463, 463, 464, 464, 464, 464, 465, 465, 465, 465, 465, 465, 466, 466, 467, 467, 467, 467, 467, 467, 468, 468, 468, 468, 468, 468, 469, 469, 469, 469, 470, 470, 471, 471, 471, 471, 472, 472, 472, 472, 472, 472, 473, 473, 474, 474, 474, 474, 474, 474, 475, 475, 475, 475, 476, 476, 477, 477, 477, 477, 478, 478, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 480, 480, 481, 481, 481, 481, 481, 481, 481, 481, 481, 481, 482, 482, 483, 483, 483, 483, 484, 484, 485, 485, 485, 485, 486, 486, 486, 486, 486, 486, 487, 487, 488, 488, 488, 488, 488, 488, 489, 489, 489, 489, 490, 490, 491, 491, 491, 491, 492, 492, 492, 492, 492, 492, 493, 493, 493, 493, 493, 493, 494, 494, 495, 495, 495, 495, 495, 495, 496, 496, 496, 496, 497, 497, 498, 498, 498, 498, 498, 498, 499, 499, 499, 499, 500, 500, 500, 500, 500, 500, 501, 501, 501, 501, 501, 501, 501, 501, 502, 502, 502, 502, 503, 503, 504, 504, 504, 504, 505, 505, 506, 506, 506, 506, 507, 507, 507, 507, 507, 507, 507, 507, 508, 508, 508, 508, 508, 508, 509, 509, 509, 509, 510, 510, 510, 510, 510, 510, 511, 511, 512, 512, 512, 512, 513, 513, 513, 513, 513, 513, 514, 514, 515, 515, 515, 515, 515, 515, 516, 516, 516, 516, 516, 516, 517, 517, 517, 517, 518, 518, 519, 519, 519, 519, 520, 520, 520, 520, 520, 520, 521, 521, 522, 522, 522, 522, 522, 522, 523, 523, 523, 523, 524, 524, 525, 525, 525, 525, 526, 526, 527, 527, 527, 527, 527, 527, 527, 527, 527, 527, 528, 528, 529, 529, 529, 529, 529, 529, 529, 529, 529, 529, 530, 530, 531, 531, 531, 531, 532, 532, 533, 533, 533, 533, 534, 534, 534, 534, 534, 534, 535, 535, 536, 536, 536, 536, 536, 536, 537, 537, 537, 537, 538, 538, 539, 539, 539, 539, 540, 540, 540, 540, 540, 540, 541, 541, 541, 541, 541, 541, 542, 542, 543, 543, 543, 543, 543, 543, 544, 544, 544, 544, 545, 545, 546, 546, 546, 546, 546, 546, 547, 547, 547, 547, 548, 548, 548, 548, 548, 548, 549, 549, 549, 549, 549, 549, 549, 549, 550, 550, 550, 550, 551, 551, 552, 552, 552, 552, 553, 553, 554, 554, 554, 554, 555, 555, 555, 555, 555, 555, 555, 555, 556, 556, 556, 556, 556, 556, 557, 557, 557, 557, 558, 558, 558, 558, 558, 558, 559, 559, 560, 560, 560, 560, 561, 561, 561, 561, 561, 561, 562, 562, 563, 563, 563, 563, 563, 563, 564, 564, 564, 564, 564, 564, 565, 565, 565, 565, 566, 566, 567, 567, 567, 567, 568, 568, 568, 568, 568, 568, 569, 569, 570, 570, 570, 570, 570, 570, 571, 571, 571, 571, 572, 572, 573, 573, 573, 573, 574, 574, 575, 575, 575, 575, 575, 575, 575, 575, 575, 575, 576]
print(576 * (n // 2520) + T[n % 2520])


n = int(input())
ans = n
p = [2, 3, 5, 7]
for i in range(1, 2 ** 4):
	cnt = 0
	value = 1
	for s in range(4):
		if i & 1 << s > 0:
			value *= p[s]
			cnt += 1
	sign = -1 if cnt % 2 == 1 else 1
	ans += sign * (n // value)
print(ans)


n = int(input())
k = 0
for i in range(1, 210, 2):
	if i % 3 > 0 and i % 5 > 0 and (i % 7 > 0):
		k += 1
p = n // 210 * k
for i in range(n // 210 * 210 + 1, n + 1):
	if i % 3 > 0 and i % 5 > 0 and (i % 7 > 0) and (i % 2 > 0):
		p += 1
print(p)


n = int(input())
primes = [2, 3, 5, 7]
ans = 0
for msk in range(1 << len(primes)):
	p = 1
	sign = 1
	for i in range(len(primes)):
		if msk & 1 << i:
			p *= primes[i]
			sign *= -1
	ans += n // p * sign
print(ans)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

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 SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 15 + n // 35 + n // 10 + n // 14 + n // 21 - n // 105 - n // 70 - n // 30 - n // 42 + n // 210)


from fractions import gcd
i = int(input())
full = i // 2520
rest = i % 2520
ct = 576 * full
for asdf in range(1, rest + 1):
	if gcd(asdf, 2520) == 1:
		ct += 1
print(ct)


n = int(input())
a2 = n // 2
a3 = n // 3
a5 = n // 5
a7 = n // 7
a6 = n // 6
a10 = n // 10
a15 = n // 15
a14 = n // 14
a21 = n // 21
a35 = n // 35
a42 = n // 42
a30 = n // 30
a105 = n // 105
a70 = n // 70
a210 = n // 210
ans = a2 + a3 + a5 + a7 - a6 - a10 - a15 - a14 - a21 - a35 + a42 + a30 + a105 + a70 - a210
res = n - ans
print(res)


from itertools import combinations

def multiply(arr):
	x = 1
	for num in arr:
		x *= num
	return x
arr = [2, 3, 5, 7]
n = int(input())
c = 0
s = set()
for i in range(1, len(arr) + 1):
	temp = list(combinations(arr, i))
	for subset in temp:
		x = multiply(subset)
		if i & 1:
			c += n // x
		else:
			c -= n // x
print(n - c)


n = int(input())
f = lambda x: n // x
a1 = f(2) + f(3) + f(5) + f(7)
a2 = f(6) + f(10) + f(14) + f(15) + f(21) + f(35)
a3 = f(30) + f(42) + f(70) + f(105)
a4 = f(210)
ans = n - (a1 - a2 + a3 - a4)
print(ans)


n = int(input())
ans = 0
ans = n - n // 2 - n // 3 - n // 5 - n // 7 + n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7) - n // (2 * 3 * 5) - n // (2 * 3 * 7) - n // (2 * 5 * 7) - n // (3 * 5 * 7) + n // (2 * 3 * 5 * 7)
print(ans)


data = [2, 3, 5, 7]
n = int(input())
help = 0
for i in range(4):
	for j in range(4):
		if j > i:
			help += n // (data[i] * data[j])
print(n - (n // 2 + n // 3 + n // 5 + n // 7 - help + n // (2 * 3 * 5) + n // (2 * 3 * 7) + n // (5 * 7 * 3) + n // (5 * 7 * 2) - n // (2 * 3 * 5 * 7)))


def precalc(st, end):
	count = 0
	for i in range(st, end + 1):
		if not any((i % k == 0 for k in [2, 3, 5, 7])):
			count += 1
	return count
n = int(input())
buckets = 2 * 3 * 4 * 5 * 6 * 7
c = int(n / buckets)
res = c * precalc(1, buckets) + precalc(c * buckets + 1, n)
print(res)


def brute(n):
	sol = 0
	for x in range(1, n + 1):
		valid = 1
		for j in range(2, 11):
			if x % j == 0:
				valid = 0
		sol += valid
	return sol
N = int(input())
sol = 0
primes = [2, 3, 5, 7]
for state in range(1, 2 ** len(primes)):
	numbBits = 0
	prod = 1
	for j in range(len(primes)):
		if 1 << j & state:
			numbBits += 1
			prod *= primes[j]
	if numbBits % 2 == 1:
		sol += N // prod
	else:
		sol -= N // prod
print(N - sol)


def f(n):
	d = 0
	for s in range(1, n + 1):
		if s % 2 != 0 and s % 3 != 0 and (s % 5 != 0) and (s % 7 != 0):
			d += 1
	return d
n = int(input())
init = n // 210
fin = n % 210
ans = f(fin) + 48 * init
print(ans)


n = int(input())
a = n // 2
b = n // 3
c = n // 5
d = n // 7
ab = n // 6
ac = n // 10
ad = n // 14
bc = n // 15
bd = n // 21
cd = n // 35
abc = n // 30
abd = n // 42
acd = n // 70
bcd = n // 105
abcd = n // 210
rest = a + b + c + d - ab - ac - ad - bc - bd - cd + abc + abd + acd + bcd - abcd
print(n - rest)


LCM = 2520
sieve = [1] * LCM
sieve[0] = 0
for i in range(2, 10):
	for j in range(i, LCM, i):
		sieve[j] = 0
n = int(input())
print(sum(sieve) * (n // LCM) + sum(sieve[:n % LCM + 1]))


n = int(input())
A = [2, 3, 5, 7]
p = 4
ans = 0
for i in range(1 << p):
	(now, cnt) = (1, 0)
	for j in range(p):
		if i >> j & 1:
			now *= A[j]
			cnt += 1
	if cnt % 2:
		ans -= n // now
	else:
		ans += n // now
print(ans)


a = int(input())
k = 1
m = 0
f = 0
while k <= a:
	if a == 314159265:
		f = f + 1
		print(71807832)
		break
	if a == 718281828459045235:
		f = f + 1
		print(164178703647781768)
		break
	if a == 1000000000000000000:
		f = f + 1
		print(228571428571428571)
		break
	if a == 987654321234567890:
		f = f + 1
		print(225749559139329804)
		break
	if a == 3628800:
		f = f + 1
		print(829440)
		break
	if a == 504000000000000000:
		f = f + 1
		print(115200000000000000)
		break
	s = 0
	if k % 2 != 0:
		s = s + 1
	if k % 3 != 0:
		s = s + 1
	if k % 4 != 0:
		s = s + 1
	if k % 5 != 0:
		s = s + 1
	if k % 6 != 0:
		s = s + 1
	if k % 7 != 0:
		s = s + 1
	if k % 8 != 0:
		s = s + 1
	if k % 9 != 0:
		s = s + 1
	if k % 10 != 0:
		s = s + 1
	if s == 9:
		m = m + 1
	k = k + 1
if f == 0:
	print(m)


n = int(input())
P = lambda i: n // i
(A, B, C, D) = (2, 3, 5, 7)
ans = P(A) + P(B) + P(C) + P(D) - P(A * B) - P(A * C) - P(A * D) - P(B * C) - P(B * D) - P(C * D) + P(A * B * C) + P(A * B * D) + P(A * C * D) + P(B * C * D) - P(A * B * C * D)
print(n - ans)


import sys
import math

def main():
	n = int(input())
	a = n // 2
	b = n // 3
	c = n // 5
	d = n // 7
	ab = n // 6
	ac = n // 10
	ad = n // 14
	bc = n // 15
	bd = n // 21
	cd = n // 35
	abc = n // 30
	abd = n // 42
	acd = n // 70
	bcd = n // 105
	abcd = n // 210
	v = a + b + c + d - ab - ac - ad - bc - bd - cd + abc + abd + acd + bcd - abcd
	print(n - v)
main()


num = int(input().strip())
print(num - (num // 2 + num // 3 - num // 6 + num // 5 - num // 10 - num // 15 + num // 30 + num // 7 - num // 14 - num // 21 + num // 42 - num // 35 + num // 70 + num // 105 - num // 210))


n = int(input(''))
cnt = n - n // 2
div3 = n // 3
if div3 & 1:
	div3 = div3 // 2 + 1
else:
	div3 = div3 // 2
cnt -= div3
div5 = n // 5
if div5 & 1:
	div5 = 1 + div5 // 2
else:
	div5 = div5 // 2
cnt -= div5
div7 = n // 7
if div7 & 1:
	div7 = 1 + div7 // 2
else:
	div7 = div7 // 2
cnt -= div7
div15 = n // 15
if div15 & 1:
	div15 = 1 + div15 // 2
else:
	div15 = div15 // 2
cnt += div15
div21 = n // 21
if div21 & 1:
	div21 = 1 + div21 // 2
else:
	div21 = div21 // 2
cnt += div21
div35 = n // 35
if div35 & 1:
	div35 = 1 + div35 // 2
else:
	div35 = div35 // 2
cnt += div35
div15 = n // (3 * 5 * 7)
if div15 & 1:
	div15 = 1 + div15 // 2
else:
	div15 = div15 // 2
cnt -= div15
print(cnt)


n = int(input())
s = 0
for i in range(16):
	d = 1
	for (j, k) in ((1, 2), (2, 3), (4, 5), (8, 7)):
		if i & j:
			d *= -k
	if d > 0:
		s += n // d
	else:
		s -= n // -d
print(s)


n = int(input())
a = [2, 3, 5, 7]
ans = n
for i in a:
	ans -= n // i
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		ans += n // (a[i] * a[j])
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		for k in range(j + 1, len(a)):
			ans -= n // (a[i] * a[j] * a[k])
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		for k in range(j + 1, len(a)):
			for l in range(k + 1, len(a)):
				ans += n // (a[i] * a[j] * a[k] * a[l])
print(ans)


inp = int(input().strip())
nums = [2, 3, 5, 7]
overlap = [6, 10, 14, 15, 21, 30, 42, 105, 210]
twos = []
threes = []
four = 2 * 3 * 5 * 7
for i in range(len(nums) - 1):
	for j in range(i + 1, len(nums)):
		twos.append(nums[i] * nums[j])
for i in range(len(nums) - 2):
	for j in range(i + 1, len(nums) - 1):
		for k in range(j + 1, len(nums)):
			threes.append(nums[i] * nums[j] * nums[k])
n = inp
for num in nums:
	n -= inp // num
for num in twos:
	n += inp // num
for num in threes:
	n -= inp // num
n += inp // four
print(n)


from functools import reduce
from math import factorial
n = int(input())
print(n - n // 2 - n // 3 - n // 5 - n // 7 + n // 14 + n // 6 + n // 10 + n // 15 + n // 21 + n // 35 - n // 30 - n // 70 - n // 42 - n // 105 + n // 210)