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 starts with an integer T (≤ 20000), denoting the number of test cases.

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

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

2

365

669

Case 1: 22

Case 2: 30

程序分析：此题的大意就是如果一间屋子里有23个，那么至少有两个人的生日相同的概率超过50%，但是如果在火星他们一年是669，这样他们超过50%的概率就是30个人，我们要做的就是输入天数计算概率超过50%至少需要多少人。

这个题目利用的排序，所以如果数字一大就会益处，我这里的这个代码就比较好的考虑到了这个情况，就是边乘边除。其次一点就是开始我的主函数的是double 型结果是CE最后改成int型才过的。

程序代码：

#include<iostream>

#include<cstdio>

using namespace std;

double birthday(int n)

 {

     double ans=1.0;

     int m=;

     for(int i=; ; i++)

     {

         ans*=(double)(n-i)/n;

         m++;

         if(1.0-ans>=0.5)

             break;

     }

     return m;

 }

int main()

{

    int T,m,j=;

        cin>>T;

    while(T--)

    {    j++;

        cin>>m;

        int k;

        k=birthday(m);

        printf("Case %d: %d\n",j,k-);

    }

    return ;

}