There is a legend in the IT City college. A student that failed to answer all questions on the game theory exam is given one more chance by his professor. The student has to play a game with the professor.

The game is played on a square field consisting of n × n cells. Initially all cells are empty. On each turn a player chooses and paint an empty cell that has no common sides with previously painted cells. Adjacent corner of painted cells is allowed. On the next turn another player does the same, then the first one and so on. The player with no cells to paint on his turn loses.

The professor have chosen the field size n and allowed the student to choose to be the first or the second player in the game. What should the student choose to win the game? Both players play optimally.


-----Input-----

The only line of the input contains one integer n (1 ≤ n ≤ 10^18) — the size of the field.


-----Output-----

Output number 1, if the player making the first turn wins when both players play optimally, otherwise print number 2.


-----Examples-----
Input
1

Output
1
Input
2

Output
2

Difficulty: EASY
Tags: Game theory

Mathematics

Starter code:

Solutions:
if int(input()) % 2 == 1:
	print(1)
else:
	print(2)


n = int(input())
n %= 2
if n == 0:
	print(2)
else:
	print(1)


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
print((not ii() & 1) + 1)


n = int(input())
print(2 - ((1 + (n - 1) // 2) ** 2 + (n - 1 - (n - 1) // 2) ** 2) % 2)


print('21'[int(input()) % 2])


from decimal import *
getcontext().prec = 100
n = Decimal(input())
if 1 == n % 2:
	print(1)
else:
	print(2)


def main():
	print(2 - (int(input()) & 1))
main()


import re, sys, string, operator, functools, fractions, collections
sys.setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda x=' ': list(map(int, input().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
mod = int(1000000000.0 + 7)
eps = 1e-06
n = RI()[0]
print(2 - (n & 1))


n = int(input())
k = n * n
if k % 2 == 0:
	print(2)
elif k % 2 != 0:
	print(1)


print([2, 1][int(input()) % 2])


from sys import stdin, stdout
from sys import maxsize
input = stdin.readline

def solve():
	pass
test = 1
for t in range(0, test):
	n = int(input().strip())
	if n & 1 == 1:
		print(1)
	else:
		print(2)
	ans = solve()


from math import factorial
print(int(not int(input()) % 2) + 1)


cosa = input()
wea = int(cosa[len(cosa) - 1])
print(2 - wea % 2)


a = int(input(''))
if a % 2 == 0:
	print(2)
else:
	print(1)


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
(n,) = list(map(int, input().split()))
print(2 - n % 2)


import math
n = int(input())
if n % 2 == 1:
	print(1)
else:
	print(2)


from sys import stdin, stdout
from math import gcd, ceil, sqrt
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()
if n % 2 == 0:
	print('2')
else:
	print('1')


print(2 - int(input()) % 2)


print(1 if int(input()) % 2 != 0 else 2)
Nothing = 0


n = int(input())
ans = 2 - n % 2
print(str(ans))


n = int(input())
n %= 2
if n == 0:
	n = 2
print(n)


import math
a = int(input())
if a % 2 == 1:
	print(1)
else:
	print(2)


x = int(input())
if x % 2 == 0:
	print(2)
else:
	print(1)


n = int(input())
ans = n * n
ans = ans // 2
if n * n % 2 == 1:
	ans += 1
ans %= 2
if ans == 1:
	print(1)
else:
	print(2)


a = int(input())
print(2 - a % 2)


import time
n = int(input())
start = time.time()
if n % 2 == 0:
	print(2)
else:
	print(1)
finish = time.time()


a = int(input()) % 2
print([2, 1][a])


m = input()
if int(m[-1]) % 2 == 0:
	print(2)
else:
	print(1)


n = int(input())
print(2 - n % 2)


import sys
import math
input = sys.stdin.readline
n = int(input())
if n % 2 == 0:
	print(2)
else:
	print(1)


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

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

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

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

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	n = int(input())
	if n % 2 == 0:
		print(2)
	else:
		print(1)
for _ in range(1):
	solve()


print(abs(int(input()) % 2 - 2))


def play(n):
	if n % 2 == 0:
		return 2
	return 1
print(play(int(input())))


x = int(input())
print(2 - (x & 1))


x = int(input()) % 2
if x == 0:
	x = 2
print(x)


print((not int(input()) % 2) + 1)


import sys
import os
a = int(input())
if a % 2 == 1:
	print(1)
else:
	print(2)


x = int(input())
a = x * x
if a % 2 == 0:
	y = '2'
else:
	y = '1'
print(y)


from functools import reduce
from math import factorial
n = int(input())
print((n - 1) % 2 + 1)


n = int(input())
print((lambda x: 1 if x % 2 else 2)(n))


n = eval(input())
if n % 2 == 0:
	print(2)
else:
	print(1)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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))
mod = 1000000007

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

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

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

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 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

def solve():
	n = int(inp())
	if n % 2 == 0:
		print(2)
	else:
		print(1)
testcase(1)


import collections, itertools, fractions, functools, heapq, math, queue

def solve():
	n = int(input())
	if n % 2 == 0:
		return 2
	return 1
print(solve())


def main():
	n = int(input())
	print(2 - n % 2)
main()


def main():
	n = input()
	n = int(n)
	if n % 2 == 0:
		print(2)
	else:
		print(1)
main()


print((int(input()) + 1 & 1) + 1)


N = int(input())
print(2 - N % 2)


w = int(input())
if w % 2 == 0:
	print('2')
else:
	print('1')


import sys

def c5(n):
	return n * (n - 1) * (n - 2) * (n - 3) * (n - 4) // 2 // 3 // 4 // 5

def c6(n):
	return c5(n) * (n - 5) // 6

def c7(n):
	return c6(n) * (n - 6) // 7
n = int(input())
print(1 if n % 2 else 2)


board_size = int(input())
temp = (board_size + 1) // 2
number = 0
if board_size % 2 == 0:
	number = temp * board_size
else:
	number = temp ** 2 + (temp - 1) * (temp - 1)
if number % 2 == 0:
	print(2)
else:
	print(1)


from sys import stdin
n = int(stdin.readline())
print(2 if n % 2 == 0 else 1)


import sys
import math

def main():
	n = int(input())
	if n % 2 == 0:
		print(2)
	else:
		print(1)
main()


game = int(input())
if game % 2 != 0:
	print(1)
else:
	print(2)


t = 1
for _ in range(t):
	n = int(input())
	if n % 2:
		print(1)
	else:
		print(2)


N = int(input())
if N % 2 == 0:
	print(2)
else:
	print(1)


z = input
mod = 10 ** 9 + 7
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f

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

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0:
			return 0
	return 1
z = input
mod = 10 ** 9 + 7
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f

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

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0:
			return 0
	return 1
n = int(z())
t = n * n
if t % 2 == 0:
	print(2)
else:
	print(1)


import sys

def fact(n):
	ret = 1
	for x in range(1, n + 1):
		ret = ret * x
	return ret

def C(n, k):
	return fact(n) // (fact(k) * fact(n - k))
n = int(input())
if n % 2 == 1:
	print(1)
else:
	print(2)


n = int(input())
s = ((n + 1) // 2) ** 2 + (n // 2) ** 2
if s % 2 == 1:
	print('1')
else:
	print('2')