Problem Description

Let L denote the number of 1s in integer D’s binary representation. Given two integers S1 and S2, we call D a WYH number if S1≤L≤S2.

With a given D, we would like to find the next WYH number Y, which is JUST larger than D. In other words, Y is the smallest WYH number among the numbers larger than D. Please write a program to solve this problem.

Input

The first line of input contains a number T indicating the number of test cases (T≤).

Each test case consists of three integers D, S1, and S2, as described above. It is guaranteed that ≤D< and D is a WYH number.

Output

For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from . Y is the next WYH number.

Sample Input

Sample Output

Case #:

Case #:

Case #: 

Source

  ACM/ICPC Asia Regional Hefei Online 

#include<stdio.h>

int main()

{

    int T,s1,s2;

    __int64 L,p;

    int cas=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%I64d%d%d",&L,&s1,&s2);

         p=(__int64)<<;

        if(L==&&s1==&&s2==){

            printf("Case #%d: 0\n",++cas);

        continue;

        }

        int flag=;

        __int64 t;

        for(int i=s1;i<=s2;i++)

        {

            int s=,f=;

            t=(__int64);

            for(int j=;j>=;j--)

            {

                if(L&((__int64)<<j))s++;

                if(s==i)

                {

                    int z,k;

                    for(k=j;k<=;k++)

                    {if(L&((__int64)<<k));

                    else {

                        t|=(__int64)<<k;

                    break;

                    }

                    }

                    z=;

                     for(int kk=k+;kk<=;kk++)

                     {

                         if(L&((__int64)<<kk))t|=(__int64)<<kk,z++;

                     }

                     z=i-z;

                     for(k=;k<=&&z>;k++)t|=(__int64)<<k,z--;

                     p=p>t?t:p; 

                f=;

                break;

                }

            }

            if(!f)

            {

                s=i-s;

                t=L;

                for(int k=;k<=&&s>;k++){

                if(L&((__int64)<<k));

                else t|=(__int64)<<k,s--;

                }

                p=p>t?t:p; 

            }

        }

        printf("Case #%d: %I64d\n",++cas,p);

    }

}