A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as "true" or "false" respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.

Examples:

Number Binary Adjacent Bits

12 1100 1

15 1111 3

27 11011 2

Input

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

Each case contains an integer N (0 ≤ N < 2³¹).

Output

For each test case, print the case number and the summation of all adjacent bits from 0 to N.

Sample Input

Output for Sample Input

7

0

6

15

20

21

22

2147483647

Case 1: 0

Case 2: 2

Case 3: 12

Case 4: 13

Case 5: 13

Case 6: 14

Case 7: 16106127360

思路與1140相似

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
vector digit;
int n;
ll pow2[32];
ll dp[32][2];
ll getSum(int pos){
    ll res = 0;
    for(int i = pos; i >= 0; i--){
        res *= 2;
        res += digit[i];
    }
    return res+1;
}
ll dfs(int pos,int pre,int zero,int done){
    if(pos==-1) return 0;
    if(!zero && !done && ~dp[pos][pre]) return dp[pos][pre];
    ll res = 0;
    int end = done?digit[pos]:1;
    for(int i = 0; i <= end; i++){
        if(pre==1&&i==1){
            if(done&&i==end){
                res += getSum(pos-1);
            }else{
                res += pow2[pos];
            }
        }
        res += dfs(pos-1,i,zero&&i==0,done&&i==end);
    }
    if(!done && !zero) dp[pos][pre] = res;
    return res;
}
ll solve(ll x){
    digit.clear();
    while(x){
        digit.push_back(x%2);
        x /= 2;
    }
    return dfs(digit.size()-1,0,1,1);
}
void init(){
    pow2[0] = 1;
    for(int i = 1; i <= 31; i++){
        pow2[i] = pow2[i-1]*2;
    }
    memset(dp,-1,sizeof dp);
}
int main(){

    int ncase,T=1;
    cin >> ncase;
    init();
    while(ncase--){
        cin >> n;
        printf("Case %d: %lld\n",T++,solve(n));
    }
    return 0;
}