You are given a set X = {1, 2, 3, 4, … , 2n-1, 2n} where n is an integer. You have to find the number of interesting subsets of this set X.

A subset of set X is interesting if there are at least two integers a & b  such that b is a multiple of a, i.e. remainder of b divides by a is zero and a is the smallest number in the set.

Input

The input file contains multiple test cases. The first line of the input is an integer T(<=30) denoting the number of test cases. Each of the next T lines contains an integer ‘n‘ where 1<=n<=1000.

Output

For each test case, you have to output as the format below:

Case X: Y 

Here X is the test case number and Y is the number of subsets. As the number Y can be very large, you need to output the number modulo 1000000007.

Example

Input:3

1

2

3Output:Case 1: 1

Case 2: 9

Case 3: 47

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e5+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;ll qpow(ll a,ll b,ll c){    ll ans=1;    while(b)    {        if(b&1)ans=(ans*a)%c;        b>>=1;        a=(a*a)%c;    }    return ans;}int main(){    int T,cas=1;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        ll ans=0;        for(int i=1;i<=n;i++)        {            int p=(2*n-i);            int b=((2*n)/i-1);            ans=(ans+(qpow(2,p-b,mod)*(qpow(2,b,mod)+(mod-1))%mod)%mod)%mod;        }        printf("Case %d: %lld\n",cas++,ans);    }    return 0;}