Determine the probability $$p_n$$ that, in a group of $$n$$ randomly chosen people, some of them will have the same birthday. If we assume that each day of the year (we exclude February 29) is equally probable for a birthday, the probability that none of the people in the group have the same birthday is given by \[ q_n = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-n+1}{365} \] The probability $$p_n$$ is then computed as $$p_n = 1-q_n$$. For the probability $$p_n \in \mathbb{R}$$, it always applies that $$0 \leq p_n \leq 1$$.

Note: The above formula is only valid for $$n \leq 365$$. What happens if $$n>365$$?

Note: By the pigeonhole principle, the probability reaches 100% when the number of people reaches 366 (since there are 365 possible birthdays, excluding February 29). However, 99% probability is reached with just 57 people, and 50% probability with 23 people. This is called the birthday paradox, not because it is a paradox in the sense of leading to a logical contradiction, but because the mathematical truth contradicts naive intuition. An intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but the birthday problem demonstrates that this is not the case.

Input

No input.

Output

For each value $$n$$ that is between 5 and 75 (boundaries included) and that is a multiple of five print the value $$n$$ itself, a single space, and then the probability $$p_n$$ that in a group of $$n$$ people at least two people have the same birthday. Use a separate line every time.

Example

5 0.0271355736998
10 0.116948177711
15 0.252901319764
...
75 0.999719878174

Epilogue

Famously, in a group of 23 randomly chosen people, the chance is slightly higher than 50 percent that two will share a birthday.

Here's an interesting variant: If the group consists of an equal number of girls and boys, what’s the minimum size at which it's probable that a girl and a boy share a birthday?

Surprisingly, the answer is only 32 (16 girls and 16 boys). If we want a girl and a boy to share the same birth month, we need only 6 children before this becomes probable.

Resources