403204: GYM101064 K Mount Rushmore and Birthdays

After going to the World Finals 2017, your team decided to stay in Rapid City for an extra week and visit some nearby attractions.

When visiting Mount Rushmore, a sculpture with the carved faces of presidents George Washington, Thomas Jefferson, Theodore Roosevelt and Abraham Lincoln, you wondered what was the chance that two of them had birthday in the same day. After a quick search on the internet, you find out that Lincoln was born on February 12 and Washington on February 11. Close enough!

The chance that in a group of 4 people 2 of them have the same birthdays is really quite low, about 1.6%. But your teammate tells you that in a group of 23 random people, the chance that some pair of them will have the same birthday is greater than 50%!

This is interesting, but if the year had a different number of days, how would this number change?

Given N, the number of days in a year, answer what is the minimum number of people needed in a room so that the chance that a pair of them has the same birthday is greater than 50%. You can assume each day has the same chance of being someone's birthday.

The input has a single integer N, the number of days in a year.

Limits

• 1 ≤ N ≤ 1000

Print a single integer, the answer to the problem.

365

23

666

31