Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. The Same Calendar

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/19/2017 01:04:30 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|