Sometimes some mathematical results are hard to believe. One of the common problems is the birthday paradox. Suppose you are in a party where there are 23 people including you. What is the probability that at least two people in the party have same birthday? Surprisingly the result is more than 0.5. Now here you have to do the opposite. You have given the number of days in a year. Remember that you can be in a different planet, for example, in Mars, a year is 669 days long. You have to find the minimum number of people you have to invite in a party such that the probability of at least two people in the party have same birthday is at least 0.5.

Input
Input starts with an integer T (≤ 20000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 105) in a single line, denoting the number of days in a year in the planet.

Output
For each case, print the case number and the desired result.

Sample Input
2
365
669
Sample Output
Case 1: 22
Case 2: 30

题意：给你一年的天数，让你算至少有多少个人时两个人生日相同的概率大于等于50%

可以了解一下生日悖论

思路：（算了期望都是倒着求的） 一波先算房间所有人生日都不同的概率。第一个人和房间内其他人生日不同的概率为365/365，第二个是364/365，第三个是363/365…第N个人是365-N+1/365，所以都不同的概率为N个人的概率相乘。故所求为1-P>=0.5

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include<algorithm>
#define N 2050
#define EPS 0.00000000001
using namespace std;
typedef long long ll;
//const int maxx=2100;

int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	scanf("%d", &T);
	int t = 1;
	while (T--)
	{
		int ans = 1;

		int n;
		scanf("%d", &n);
		double p=1.0 ,sum=0;
		for (int i = n-1; i > 0; i--)
		{
			p*=(double) (i*1.0)/ (double)(n*1.0);
			
			if (1-p>=0.5)
			{
				break;
			}
			ans++;

		
		}
		printf("Case %d: %d\n", t++, ans);
	}

	return 0;


}