Vasya started working in a machine vision company of IT City. Vasya's team creates software and hardware for identification of people by their face.

One of the project's know-how is a camera rotating around its optical axis on shooting. People see an eye-catching gadget — a rotating camera — come up to it to see it better, look into it. And the camera takes their photo at that time. What could be better for high quality identification?

But not everything is so simple. The pictures from camera appear rotated too (on clockwise camera rotation frame the content becomes rotated counter-clockwise). But the identification algorithm can work only with faces that are just slightly deviated from vertical.

Vasya was entrusted to correct the situation — to rotate a captured image so that image would be minimally deviated from vertical. Requirements were severe. Firstly, the picture should be rotated only on angle divisible by 90 degrees to not lose a bit of information about the image. Secondly, the frames from the camera are so huge and FPS is so big that adequate rotation speed is provided by hardware FPGA solution only. And this solution can rotate only by 90 degrees clockwise. Of course, one can apply 90 degrees turn several times but for the sake of performance the number of turns should be minimized.

Help Vasya implement the program that by the given rotation angle of the camera can determine the minimum number of 90 degrees clockwise turns necessary to get a picture in which up direction deviation from vertical is minimum.

The next figure contains frames taken from an unrotated camera, then from rotated 90 degrees clockwise, then from rotated 90 degrees counter-clockwise. Arrows show direction to "true up". [Image] 

The next figure shows 90 degrees clockwise turn by FPGA hardware. [Image] 


-----Input-----

The only line of the input contains one integer x ( - 10^18 ≤ x ≤ 10^18) — camera angle in degrees. Positive value denotes clockwise camera rotation, negative — counter-clockwise.


-----Output-----

Output one integer — the minimum required number of 90 degrees clockwise turns.


-----Examples-----
Input
60

Output
1

Input
-60

Output
3



-----Note-----

When the camera is rotated 60 degrees counter-clockwise (the second example), an image from it is rotated 60 degrees clockwise. One 90 degrees clockwise turn of the image result in 150 degrees clockwise total rotation and deviation from "true up" for one turn is 150 degrees. Two 90 degrees clockwise turns of the image result in 240 degrees clockwise total rotation and deviation from "true up" for two turns is 120 degrees because 240 degrees clockwise equal to 120 degrees counter-clockwise. Three 90 degrees clockwise turns of the image result in 330 degrees clockwise total rotation and deviation from "true up" for three turns is 30 degrees because 330 degrees clockwise equal to 30 degrees counter-clockwise.

From 60, 150, 120 and 30 degrees deviations the smallest is 30, and it it achieved in three 90 degrees clockwise turns.

Difficulty: MEDIUM_HARD
Tags: Geometry

Mathematics

Starter code:

Solutions:
x = int(input()) % 360
a = [min(abs(x), abs(x - 360))] + [abs(x - y) for y in range(90, 360, 90)]
print(a.index(min(a)))


def sign(x):
	return 1 if x > 0 else -1

def dis(x):
	if x >= 360:
		x %= 360
	if x <= -180:
		return 360 + x
	elif x <= 0:
		return abs(x)
	elif x <= 180:
		return x
	else:
		return 360 - x

def __starting_point():
	x = int(input())
	x = -sign(x) * (abs(x) % 360)
	mindis = dis(x)
	res = 0
	for i in range(1, 4):
		newdis = dis(x + 90 * i)
		if newdis < mindis:
			mindis = newdis
			res = i
	print(res)
__starting_point()


angle = int(input())
angle = (angle % 360 + 360) % 360
angle = (angle + 44) % 360
answer = angle % 359 // 90
print(answer)


n = int(input())
n = (n % 360 + 360) % 360
n = (n + 44) % 360
print(n % 359 // 90)


ang = int(input())
ang -= 360 * (ang // 360)
if not 0 <= ang < 360:
	exit(1)
cnt = 0
while ang > 45 and ang < 360 - 45:
	ang -= 90
	cnt += 1
print(cnt)


n = int(input()) % 360
v1 = n // 90
v2 = v1 + 1
if v2 < 4:
	if n - 90 * v1 > 90 * v2 - n:
		print(v2)
	else:
		print(v1)
elif n - 90 * v1 < 360 - n:
	print(v1)
else:
	print('0')


n = (int(input()) + 45) % 360
if n % 90 == 0 and n != 0:
	print(n // 90 - 1)
else:
	print(n // 90)


n = -int(input())
n %= 360
f = lambda n: 360 - n if n >= 180 else n
r = [f((n + 90 * i) % 360) for i in range(4)]
for i in range(4):
	if r[i] == min(r):
		print(i)
		break


n = (360 + int(input()) % 360) % 360
ans = 0
bres = n
for i in range(1, 5):
	d = (360 + (n - i * 90) % 360) % 360
	if min(d, 360 - d) < min(bres, 360 - bres):
		bres = d
		ans = i
print(ans)


n = int(input()) % 360
print((abs(n - 360) > 45) * (n // 90 + int(round(n % 90 / 90))))


x = int(input())
v = 0
a = []
for i in range(4):
	angle = ((i * 90 - x) % 360 + 360) % 360
	a.append(min(angle, 360 - angle))
	if a[i] < a[v]:
		v = i
print(v)


def main():
	n = int(input()) % 360
	print((n + (44 if n < 271 else 45)) // 90 % 4)
main()


import sys
import math

def main():
	n = int(input())
	n = -n
	n %= 360
	a = n
	a1 = 360 - a
	b = (a + 90) % 360
	b1 = 360 - b
	c = (b + 90) % 360
	c1 = 360 - c
	d = (c + 90) % 360
	d1 = 360 - d
	ans = min([a, a1, b, b1, c, c1, d, d1])
	if a == ans or a1 == ans:
		print(0)
	elif b == ans or b1 == ans:
		print(1)
	elif c == ans or c1 == ans:
		print(2)
	elif d == ans or d1 == ans:
		print(3)
main()


a = -int(input())
a %= 360
c = min(a, 360 - a, (a + 90) % 360, abs(360 - (a + 90) % 360), (a + 180) % 360, abs(360 - (a + 180) % 360), (a + 270) % 360, abs(360 - (a + 270) % 360))
if c == min(a, 360 - a):
	print(0)
elif c == min((a + 90) % 360, abs(360 - (a + 90) % 360)):
	print(1)
elif c == min((a + 180) % 360, abs(360 - (a + 180) % 360)):
	print(2)
else:
	print(3)


n = int(input().strip())
n %= 360
cnt = 0
opt = min(n, abs(360 - n))
for i in range(4):
	n = (n - 90) % 360
	x = min(n, abs(360 - n))
	if opt > x:
		opt = x
		cnt = i + 1
print(cnt)


def f(x):
	assert 0 <= x <= 360
	return min(x, 360 - x)

def main():
	x = int(input())
	(a, b, c, d) = (-x, -x + 90, -x + 180, -x + 270)
	(a, b, c, d) = (a % 360, b % 360, c % 360, d % 360)
	(a, b, c, d) = (f(a), f(b), f(c), f(d))
	L = [(a, 0), (b, 1), (c, 2), (d, 3)]
	L.sort()
	print(L[0][1])

def __starting_point():
	main()
__starting_point()


x = int(input())
x %= 360
if x < 0:
	x += 360
if 46 <= x <= 135:
	print(1)
elif 136 <= x <= 225:
	print(2)
elif 226 <= x < 315:
	print(3)
else:
	print(0)


print(max(((int(input()) + 45) % 360 - 1) // 90, 0))


x = int(input())
x = (x % 360 + 360) % 360
x = (x + 44) % 360
x = x % 359 // 90
print(x)


n = (int(input()) + 360 * 10 ** 18) % 360
ans = [0] * 4
for i in range(4):
	ans[i] = min(abs(n - 90 * i), abs(360 - n + 90 * i))
m = min(ans)
for i in range(4):
	if ans[i] == m:
		print(i)
		break


n = int(input())
rot = n - 360 * (n // 360)
if rot <= 45 or rot >= 315:
	print(0)
if rot > 45 and rot <= 135:
	print(1)
if rot > 135 and rot <= 225:
	print(2)
if rot > 225 and rot < 315:
	print(3)


from sys import stdin
n = -int(stdin.readline())
n = n % 360
if n <= 45:
	print('0')
elif 45 < n < 135:
	print('3')
elif 135 <= n < 225:
	print('2')
elif 225 <= n < 315:
	print('1')
else:
	print('0')


import math
x = int(input())
x %= 360
x = 360 - x
curnum = x
for i in range(4):
	if curnum <= 45:
		print(i)
		quit()
	if 360 - curnum <= 45:
		print(i)
		quit()
	curnum = (curnum + 90) % 360


n = -int(input()) % 360
(ret, opt) = (4, 361)
for i in range(4):
	x = (n + 90 * i) % 360
	x = min(x, 360 - x)
	if (x, i) < (opt, ret):
		(opt, ret) = (x, i)
print(ret)


n = int(input())
ans = 0
n %= 360
if n <= 45 or n >= 270:
	ans = 0
if n > 45 and n <= 135:
	ans = 1
if n > 135 and n <= 225:
	ans = 2
if n > 225 and n < 315:
	ans = 3
print(ans)


x = int(input())
x %= 360
if x <= 45 or x >= 315:
	print(0)
elif x <= 135:
	print(1)
elif x <= 225:
	print(2)
else:
	print(3)


n = int(input())
n = n * -1 % 360
minVueltas = -1
minValor = -1
for i in range(4):
	temp = (n + 90 * i) % 360
	if temp > 180:
		temp = 360 - temp
	if minValor == -1 or temp < minValor:
		minVueltas = i
		minValor = temp
print(minVueltas)


n = int(input()) % 360
if 45 < n <= 135:
	print(1)
elif 135 < n <= 225:
	print(2)
elif 225 < n < 315:
	print(3)
else:
	print(0)


x = int(input())
x = 360 * 10 ** 16 + x
x %= 360
ans_i = -1
ans_x = 100000
for i in range(4):
	dx = min(x, 360 - x)
	if dx < ans_x:
		ans_i = i
		ans_x = dx
	x = 270 + x
	x %= 360
print(ans_i)


import math
x = int(input()) % 360
minimum = min(abs(x), 360 - abs(x))
ans = 0
for i in range(1, 4):
	x -= 90
	if min(abs(x), 360 - abs(x)) < minimum:
		minimum = min(abs(x), 360 - abs(x))
		ans = i
print(ans)


n = int(input())
n += 90
n %= 360
ans = [n, (n - 90) % 360, (n - 180) % 360, (n - 270) % 360]
for i in range(len(ans)):
	ans[i] = min(abs(90 - ans[i]), abs(450 - ans[i]))
print(ans.index(min(ans)))


import math
a = int(input())
a %= 360
m = min(a % 360, 360 - a % 360)
mi = 0
for i in range(1, 4):
	if m > min(360 - abs(a - 90 * i), abs(a - 90 * i)):
		m = min(360 - abs(a - 90 * i), abs(a - 90 * i))
		mi = i
print(mi)


n = int(input())
t = n - n // 360 * 360
i = 0
while not (-45 <= t <= 45 or 315 <= t <= 360):
	i += 1
	t -= 90
print(i)


def norm(n):
	return (n % 360 + 360) % 360

def rot(n, angle):
	return norm(n + angle)

def better(a, b):
	if a > 180:
		a = 360 - a
	if b > 180:
		b = 360 - b
	return a < b
n = int(input())
n = norm(n)
val = [(rot(n, 0), 0), (rot(n, -90), 1), (rot(n, 180), 2), (rot(n, 90), 3)]
pos = 0
for i in range(4):
	if better(val[i][0], val[pos][0]):
		pos = i
print(val[pos][1])


x = int(input())
x = (x % 360 + 360) % 360
ans = 0
while x > 45 and x < 315:
	ans += 1
	x -= 90
print(ans)


x = -int(input()) % 360
l = [x, x + 90, x + 180, x + 270]
l = [min(x % 360, -x % 360) for x in l]
m = min(l)
print(l.index(m))


def povorot(n):
	n = (n % 360 + 360) % 360
	n = (n + 44) % 360
	return n % 359 // 90
print(povorot(int(input())))


def main():
	n = int(input())
	n = (-n % 360 + 360) % 360
	if n <= 45:
		print(0)
	else:
		ans = 0
		if n % 90 < 45:
			ans += 1
		ans += 3 - n // 90
		print(ans)
main()


from functools import reduce
from math import factorial
n = (int(input()) + 45) % 360
print(n // 90 - (n > 0 and n % 90 == 0))


import math, 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
x = RI()[0]
x %= 360
if x > 180:
	x = x - 360
ans = 0
val = abs(x)
for i in range(1, 4):
	x -= 90
	if x < -180:
		x = 360 + x
	if abs(x) < val:
		val = abs(x)
		ans = i
print(ans)


n = int(input())
if n < 0:
	n = 360 - abs(n) % 360
n %= 360
if n >= 315:
	print(0)
	exit(0)
r = 0
while n > 45:
	r += 1
	n -= 90
print(r)


import sys
n = int(sys.stdin.readline())
n %= 360
_0 = min(360 - n, n)
n = (n - 90) % 360
_1 = min(360 - n, n)
n = (n - 90) % 360
_2 = min(360 - n, n)
n = (n - 90) % 360
_3 = min(360 - n, n)
if _0 <= min(_1, min(_2, _3)):
	print(0)
	return
if _1 <= min(_0, min(_2, _3)):
	print(1)
	return
if _2 <= min(_1, min(_0, _3)):
	print(2)
	return
if _3 <= min(_1, min(_2, _0)):
	print(3)
	return


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()))
angle = ((n + 45) % 360 + 360) % 360
if angle <= 90:
	print(0)
elif angle <= 180:
	print(1)
elif angle <= 270:
	print(2)
else:
	print(3)


n = int(input()) % 360
if n <= 45:
	print(0)
elif n <= 90 + 45:
	print(1)
elif n <= 180 + 45:
	print(2)
elif n < 270 + 45:
	print(3)
else:
	print(0)


D = int(input())
D = -D
D = D % 360
print((404 - D) // 90 if D > 45 else 0)


n = int(input())

def get(t):
	t = t % 360
	return min(t, 360 - t)
mn = get(n)
cnt = 0
for i in range(4):
	x = n - 90 * i
	if mn > get(x):
		mn = get(x)
		cnt = i
print(cnt)


n = int(input()) % 360
n -= 360 * (n >= 180)
n += 360 * (n < -180)
print(sorted([(abs(n - 0 + 360 * (n - 0 < -180)), 0), (abs(n - 90 + 360 * (n - 90 < -180)), 1), (abs(n - 180 + 360 * (n - 180 < -180)), 2), (abs(n - 270 + 360 * (n - 270 < -180)), 3)])[0][1])


from sys import stdin, stdout

def dist(current):
	mod = current % 360
	return min(mod, 360 - mod)

def main():
	d = int(stdin.readline())
	best_i = 0
	best_d = dist(d)
	for i in range(4):
		new = dist(d - 90 * i)
		if new < best_d:
			best_i = i
			best_d = new
	print(best_i)
main()


import sys

def chet(a, b):
	ans = (b - a) // 2
	if b % 2 == 0 or a % 2 == 0:
		ans += 1
	return ans

def nechet(a, b):
	ans = (b - a) // 2
	if b % 2 == 1 or a % 2 == 1:
		ans += 1
	return ans

def ans(a, b, c, d):
	return chet(a, c) * chet(b, d) + nechet(a, c) * nechet(b, d)
n = int(input())
ras = n // 360
k = n - 360 * ras
ost = (k + 45) % 90
d = (k + 45) // 90
ans = d if ost > 0 or d % 4 == 0 else d - 1
print(ans % 4)


n = int(input())
ang = (n % 360 + 360) % 360
ang = (ang + 44) % 360
ans = ang % 359 // 90
print(ans)


def fu(a):
	a = a % 360
	return min(360 - a, a)
x = int(input()) % 360
a = [[fu(x), 0], [fu(x - 90), 1], [fu(x - 180), 2], [fu(x - 270), 3], [fu(x - 360), 4]]
print(min(a)[1])


n = int(input())
n += 3600000000000000000000
x = n % 360
if x <= 45:
	print(0)
elif x <= 135:
	print(1)
elif x <= 225:
	print(2)
elif x < 315:
	print(3)
elif x >= 315:
	print(0)