Problem Description

For a decimal number x with n digits (A_nA_n-1A_n-2 ... A₂A₁), we define its weight as F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

 

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 10⁹)

 

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

liuyiding

 

/* ***********************************************

Author        :kuangbin

Created Time  :2013/9/14 星期六 12:45:42

File Name     :2013成都网络赛\1007.cpp

************************************************ */

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int dp[][];

int bit[];

int dfs(int pos,int num,bool flag)

{

    if(pos == -)return num >= ;

    if(num < )return ;

    if(!flag && dp[pos][num] != -)

        return dp[pos][num];

    int ans = ;

    int end = flag?bit[pos]:;

    for(int i = ;i <= end;i++)

    {

        ans += dfs(pos-,num - i*(<<pos),flag && i==end);

    }

    if(!flag)dp[pos][num] = ans;

    return ans;

}

int F(int x)

{

    int ret = ;

    int len = ;

    while(x)

    {

        ret += (x%)*(<<len);

        len++;

        x /= ;

    }

    return ret;

}

int A,B;

int calc()

{

    int len = ;

    while(B)

    {

        bit[len++] = B%;

        B/=;

        //cout<<bit[len-1]<<endl;

    }

    //cout<<F(A)<<endl;

    return dfs(len-,F(A),);

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

    int iCase = ;

    scanf("%d",&T);

    memset(dp,-,sizeof(dp));

    while(T--)

    {

        iCase++;

        scanf("%d%d",&A,&B);

        printf("Case #%d: %d\n",iCase,calc());

    }

    return ;

}