#include <bits/stdc++.h>
using namespace std;
long long sigma(long long n) { return (n * (n + 1) / 2); }
long long MOD(long long x) {
  if (x >= 0) return x;
  return (-x);
}
bool great(long long a, long long b) { return a > b; }
bool p_sm(pair<long long, long long> a, pair<long long, long long> b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
long long max3(long long a, long long b, long long c) {
  return (max(a, max(b, c)));
}
long long max4(long long a, long long b, long long c, long long d) {
  return (max(max(a, b), max(c, d)));
}
long long min3(long long a, long long b, long long c) {
  return (min(a, min(b, c)));
}
long long min4(long long a, long long b, long long c, long long d) {
  return (min(min(a, b), min(c, d)));
}
vector<long long> factors(long long x) {
  vector<long long> v;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      v.push_back(i);
      if (i != x / i) {
        v.push_back(x / i);
      }
    }
  }
  return v;
}
vector<long long> ispr;
vector<long long> min_prime;
unordered_map<long long, long long> prime_fact(long long x) {
  unordered_map<long long, long long> mp;
  while (x != 1) {
    mp[min_prime[x]]++;
    x /= min_prime[x];
  }
  return mp;
}
map<long long, long long> factorizee(long long n) {
  map<long long, long long> mp;
  for (long long i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      mp[i]++;
      n /= i;
    }
  }
  if (n != 1) {
    mp[n]++;
  }
  return mp;
}
long long power(long long a, long long b, long long m) {
  long long ans = 1;
  while (b > 0) {
    if (b % 2) {
      ans = (ans * a) % m;
    }
    a = (a * a) % m;
    b = b / 2;
  }
  return ans;
}
bool f(long long n) {
  if ((n % 400) == 0) {
    return true;
  }
  if ((n % 100) && !(n % 4)) {
    return true;
  }
  return false;
}
int main() {
  long long n;
  cin >> n;
  long long nn = n;
  long long ans = 0;
  long long ff = 0;
  while (1) {
    if ((!ff) && (nn != n)) {
      if (!f(n)) {
        if (!f(nn)) {
          cout << nn << endl;
          exit(0);
          ;
        }
      } else {
        if (f(nn)) {
          cout << nn << endl;
          exit(0);
          ;
        }
      }
    }
    if (!f(nn)) {
      ff += 1;
      ff %= 7;
    } else {
      ff += 2;
      ff %= 7;
    }
    nn++;
    ans++;
  }
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long sigma(long long n) { return (n * (n + 1) / 2); }
long long MOD(long long x) {
  if (x >= 0) return x;
  return (-x);
}
bool great(long long a, long long b) { return a > b; }
bool p_sm(pair<long long, long long> a, pair<long long, long long> b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
long long max3(long long a, long long b, long long c) {
  return (max(a, max(b, c)));
}
long long max4(long long a, long long b, long long c, long long d) {
  return (max(max(a, b), max(c, d)));
}
long long min3(long long a, long long b, long long c) {
  return (min(a, min(b, c)));
}
long long min4(long long a, long long b, long long c, long long d) {
  return (min(min(a, b), min(c, d)));
}
vector<long long> factors(long long x) {
  vector<long long> v;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      v.push_back(i);
      if (i != x / i) {
        v.push_back(x / i);
      }
    }
  }
  return v;
}
vector<long long> ispr;
vector<long long> min_prime;
unordered_map<long long, long long> prime_fact(long long x) {
  unordered_map<long long, long long> mp;
  while (x != 1) {
    mp[min_prime[x]]++;
    x /= min_prime[x];
  }
  return mp;
}
map<long long, long long> factorizee(long long n) {
  map<long long, long long> mp;
  for (long long i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      mp[i]++;
      n /= i;
    }
  }
  if (n != 1) {
    mp[n]++;
  }
  return mp;
}
long long power(long long a, long long b, long long m) {
  long long ans = 1;
  while (b > 0) {
    if (b % 2) {
      ans = (ans * a) % m;
    }
    a = (a * a) % m;
    b = b / 2;
  }
  return ans;
}
bool f(long long n) {
  if ((n % 400) == 0) {
    return true;
  }
  if ((n % 100) && !(n % 4)) {
    return true;
  }
  return false;
}
int main() {
  long long n;
  cin >> n;
  long long nn = n;
  long long ans = 0;
  long long ff = 0;
  while (1) {
    if ((!ff) && (nn != n)) {
      if (!f(n)) {
        if (!f(nn)) {
          cout << nn << endl;
          exit(0);
          ;
        }
      } else {
        if (f(nn)) {
          cout << nn << endl;
          exit(0);
          ;
        }
      }
    }
    if (!f(nn)) {
      ff += 1;
      ff %= 7;
    } else {
      ff += 2;
      ff %= 7;
    }
    nn++;
    ans++;
  }
}

```