The girl Taylor has a beautiful calendar for the year y. In the calendar all days are given with their days of week: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday.

The calendar is so beautiful that she wants to know what is the next year after y when the calendar will be exactly the same. Help Taylor to find that year.

Note that leap years has 366 days. The year is leap if it is divisible by 400 or it is divisible by 4, but not by 100 (https://en.wikipedia.org/wiki/Leap_year).


-----Input-----

The only line contains integer y (1000 ≤ y < 100'000) — the year of the calendar.


-----Output-----

Print the only integer y' — the next year after y when the calendar will be the same. Note that you should find the first year after y with the same calendar.


-----Examples-----
Input
2016

Output
2044

Input
2000

Output
2028

Input
50501

Output
50507



-----Note-----

Today is Monday, the 13th of June, 2016.

Difficulty: interview

Starter code:

Solutions:
def iswis(a):
	return a % 400 == 0 or (a%100!= 0 and a %4==0)

n = int(input())
wis = iswis(n)
fr = 0;
n += 1
if (wis):
	fr += 1
fr += 1
while (iswis(n) != wis or fr != 0):
	if (iswis(n)):
		fr += 1
	fr += 1
	fr %= 7
	n += 1
print(n)

def is_leap(n):
    return n % 400 == 0 or (n % 4 == 0 and n % 100 != 0)

curr = int(input())
leapness = is_leap(curr)
first = 0
while True:
    if is_leap(curr):
        first += 1
    first += 1
    first %= 7
    curr += 1
    if first == 0 and leapness == is_leap(curr):
        break
print(curr)

a = int(input())
aa = a
c = 0
if (a % 400 == 0 or (a % 100 != 0 and a % 4 == 0)):
    c = 366
else:
    c = 365
a += 1
while c % 7 != 0 or (a % 400 == 0 or (a % 100 != 0 and a % 4 == 0)) != (aa % 400 == 0 or (aa % 100 != 0 and aa % 4 == 0)):
    if (a % 400 == 0 or (a % 100 != 0 and a % 4 == 0)):
        c += 366
    else:
        c += 365
    a += 1
print(a)

def days(year):
	if year % 400 == 0:
		return 366
	if year % 4 == 0 and year % 100 != 0:
		return 366
	return 365

year = int(input())
f = days(year)
t = days(year) % 7
year += 1
while True:
	if t == 0 and days(year) == f:
		print(year)
		return
	t += days(year)
	t %= 7
	year += 1




#!/usr/bin/env python3

def is_leap(y):
    return bool(not y % 400 or (not y & 0x3 and y % 100))

try:
    while True:
        y = int(input())
        prev_leap = initial_leap = is_leap(y)
        m = 0
        while True:
            if prev_leap:
                m += 2
            else:
                m += 1
            m %= 7
            y += 1
            prev_leap = is_leap(y)
            if not m and prev_leap == initial_leap:
                print(y)
                break

except EOFError:
    pass


n = int(input())
num = 0
if n % 400 == 0 or (n % 4 == 0 and n % 100 != 0):
    num = 1
n2 = n + 1
num2 = 365 + num
while True:
    num3 = 0
    if n2 % 400 == 0 or (n2 % 4 == 0 and n2 % 100 != 0):
        num3 = 1
    if num2 % 7 == 0:
        if num3 == num:
            break
    num2 += 365 + num3
    n2 += 1
print(n2)


def is_leap(year):
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)


def year_days(year):
    return 365 + int(is_leap(year))


y = int(input().strip())
offset = 0
res = y
while 1:
    if offset and offset % 7 == 0 and is_leap(y) == is_leap(res):
        break

    offset += year_days(res) % 7
    res += 1

print(res)


leap = lambda k: (k % 4 == 0 and k % 100 != 0) or k % 400 == 0

y = int(input())
if leap(y): flag = True
else: flag = False
d = 7
x = y
d2, flag2 = d, flag
while 1:
    x += 1
    d2 -= 1
    if leap(x):
        d2 -= 1
        flag2 = True
    else:
        flag2 = False
    if d2 <= 0: d2 += 7
    if (d2, flag2) == (d, flag):
        break
print(x)

import datetime

def tot_days(year):
    if year % 400 == 0: return 366
    if year % 100 == 0: return 365
    if year % 4 == 0: return 366
    return 365

year = int(input())

first_day = 0
tot = tot_days(year)

days = first_day
cyear = year

while True:
    days = (days + tot_days(cyear)) % 7
    cyear += 1

    if first_day == days and tot == tot_days(cyear):
        print(cyear)
        break


y = int(input())

def is_leap(y):
    return y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)

def days(y):
    return 365 if not is_leap(y) else 366

shift = days(y) % 7
for ny in range(y + 1, 200000):
    if is_leap(ny) == is_leap(y) and shift == 0:
        print(ny)
        break
    else:
        shift = (shift + days(ny)) % 7


def days(year):
    if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0:
        return 366
    return 365


y = int(input())
y_next = y + 1
first_day_next = days(y + 1) % 7
while first_day_next != 0 or days(y) != days(y_next):
    y_next += 1
    first_day_next = (first_day_next + days(y_next) % 7) % 7
print(y_next)

def number_of_days(year):
    if year % 400 == 0:
        return 366
    if year % 4 == 0 and year % 100 != 0:
        return 366
    return 365

y = int(input())

number_of_days_in_y = number_of_days(y)

total = number_of_days(y)

while True:
    if total % 7 == 0 and number_of_days_in_y == number_of_days(y+1):
        print(y+1)
        break
    y += 1
    total += number_of_days(y)


#B
y=int(input())

def visok_y(y):
    if ((y%4==0) and (y%100!=0)) or (y%400==0):
        return 2
    else:
        return 1
y_v=visok_y(y)
day=0

while True:
    day=(day+visok_y(y))%7
    y+=1
    if day==0 and visok_y(y)==y_v:
        print(y)
        break


def leap(x):
    return x % 400 == 0 or x % 4 == 0 and x % 100 != 0

y, v = int(input()), 0
l = leap(y)
while True:
    v = (v + 1 + leap(y)) % 7
    y += 1
    if v == 0 and leap(y) == l:
        print(y)
        break

def leap(y):
    return y % 400 == 0 or y % 4 == 0 and y % 100 != 0

sun,mon,tue,wed,thu,fri,sat = [i for i in range(7)]
l = {i:0 for i in range(1000,110000)}
l[2016] = fri
for i in range(2015, 999, -1):
    if leap(i):
        l[i] = (7+l[i+1]-2)%7
    else:
        l[i] = (7+l[i+1]-1)%7

for i in range(2017, 110000):
    if leap(i-1):
        l[i] = (l[i-1] + 2)%7
    else:
        l[i] = (l[i-1] + 1)%7

year = int(input())
for i in range(year+1, 110000):
    if l[i] == l[year] and leap(i) == leap(year):
        print(i)
        break


def f(n):
    if n % 400 == 0:
        return True
    elif n % 100 == 0:
        return False
    elif n % 4 == 0:
        return True
    else:
        return False
n = int(input())
N = n
c = 0
while True:
    n += 1
    if f(n):
        c += 2
    else:
        c += 1
    if c % 7 == 0 and f(n) == f(N):
        break
print(n)
    


day = 0
y = int(input())
leap = y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)

y += 1
days = 366%7 if y % 400 == 0 or (y % 4 == 0 and y % 100 != 0) else 365%7
day = (day + days)%7

while True:
    if day == 0:
        this_leap = y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)
        if leap == this_leap:
            break
        
    y += 1
    days = 366%7 if y % 400 == 0 or (y % 4 == 0 and y % 100 != 0) else 365%7
    day = (day + days)%7

print(y)

from datetime import datetime
def is_leap(y):
    return bool((not (y % 4) and (y % 100)) or not (y % 400))
y = int(input())
z = 0
x = y
while True:
    x += 1
    if is_leap(x):
        z += 2
    else:
        z += 1
    if (z % 7) == 0 and is_leap(x) == is_leap(y):
        break
print(x)


y = int(input())

d = 1


def is_v(year):
    if year % 400 == 0 or (year % 4 == 0 and year % 100 != 0):
        return True
    else:
        return False

v = is_v(y)

while True:
    y += 1
    if is_v(y):
        d += 2
    else:
        d += 1

    if d > 7:
        d -= 7

    if d == 1 and is_v(y) == v:
        print(y)
        break


3
# Copyright (C) 2016 Sayutin Dmitry.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; version 3
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; If not, see <http://www.gnu.org/licenses/>.

def is_leap(year):
    return (year % 400 == 0 or (year % 100 != 0 and year % 4 == 0))

def main():
    year = int(input())
    newyear = year
    delta = 0
    
    while newyear == year or not (delta == 0 and is_leap(year) == is_leap(newyear)):
        delta += (365 + int(is_leap(newyear)))
        delta %= 7
        newyear += 1
    print(newyear)

main()


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

def func(y):
    if (y % 400 == 0 ) or ((y % 4 == 0) and (y%100 != 0)) :
        return 2
    return 1

y   = int(input())

start = time.time()

sum = 0
now = func(y)
f   = 0

while ((sum %7 != 0) or (now != f)):
    y = y + 1
    f = func(y)
    sum = sum + f

print(y)
finish = time.time()
#print(finish - start)


n = int(input())
st = n
vis = n % 400 == 0 or n % 4 == 0 and n % 100 != 0
now = 7
while now != 0 or vis != (n % 400 == 0 or n % 4 == 0 and n % 100 != 0):
    n += 1
    if n % 400 == 0 or n % 4 == 0 and n % 100 != 0:
        now += 2
        now %= 7
    else:
        now = (now + 1) % 7
print(n)




def estBissextile(annee):
        if annee%400==0 or (annee%4==0 and annee%100!=0):
                return True
        return False

annee=int(input())

if not estBissextile(annee):
        compteur=1
        annee+=1
        while  compteur%7!=0 or estBissextile(annee):
                if estBissextile(annee):
                        compteur+=2
                else:
                        compteur+=1
                annee+=1
else:
        compteur=2
        annee+=1
        while compteur%7!=0 or not estBissextile(annee):
                if estBissextile(annee):
                        compteur+=2
                else:
                        compteur+=1
                annee+=1

print(annee)


def days(n):
    if n%400==0 or n%4==0 and n%100!=0:
        return 366
    else:
        return 365

n = int(input())
leap = days(n)

inicial=0
for act in range(n+1,1000000000+1):
    inicial=(inicial+days(act)%7)%7
    if inicial==0 and days(act)==leap:
        print(act)
        break