#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<long long, null_type,less<>, rb_tree_tag,tree_order_statistics_node_update>

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using mll = map<ll,ll>;
using sll = set<ll>;
#define iv(v) for(auto &i:v) cin >> i
#define ov(v) for(auto &i:v) cout << i << " "
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES\n"
#define no cout << "NO\n"

#ifdef ONLINE_JUDGE
#define Bismillah ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#else
#define Bismillah ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); \
freopen("in.txt", "r", stdin); \
freopen("out.txt", "w", stdout);
#endif

const ll MOD = 1e9 + 7;

ll add(ll a, ll b) {return ((a % MOD) + (b % MOD)) % MOD;}
ll mul(ll a, ll b) {return ((a % MOD) * (b % MOD)) % MOD;}
ll sub(ll a, ll b) {return (((a - b) % MOD) + MOD) % MOD;}
ll modExp(ll a, ll b) {
    if (b <= 0) return 1;
    ll ret = modExp(a * a % MOD, b / 2);
    if (b % 2) ret = ret * a % MOD;
    return ret;
}
ll inverse(ll b) {return modExp(b, MOD - 2);}
ll divv(ll a, ll b) {return ((a % MOD) * (inverse(b) % MOD)) % MOD;}
const ll N=1e7+1;

ll spf[N];
#define ll int

void sieve(int n){
    for(ll i=1;i<=n;i++)spf[i]=i;
    for(int i = 2; i * i <= n; i++){
        if(spf[i]==i){
            for(int j = i * i; j <= n; j += i)
                if(spf[j]==j)spf[j]=i;
        }
    }
}

ll countDivisors(ll n) {
    ll ans=1;
    while (n>1) {
        ll p=spf[n];
        ll count=0;
        while (n%p==0) {
            n/=p;
            count++;
        }
        ans*=(count+1);
    }
    return ans;
}


vector<int> divisors(int x){
    vector<pair<int,int>> f;
    while(x>1){
        int p=spf[x], c=0;
        while(x%p==0){ x/=p; c++; }
        f.push_back({p,c});
    }
    vector<int> divs = {1};
    for(auto &p:f){
        int sz=divs.size();
        for(int i=0;i<sz;i++){
            int val = divs[i];
            for(int k=0;k<p.second;k++){
                val *= p.first;
                divs.push_back(val);
            }
        }
    }
    sort(divs.begin(), divs.end());
    return divs;
}
void solve() {

}

int main() {
    Bismillah
    ll t=1;
    cin >> t;
    vector<ll> v(1e5 + 1);
    v[0] = 0;
    v[1] = v[2] = v[3] = 1;
    for (int i = 4; i <= 1e5; i++) v[i] = (v[i - 1] + v[i - 3]) % MOD;
    int i = 1;
    while (t--) {
        //solve();
        ll k, n;
        cin >> k >> n;
        cout << "Case " << i << ": " << ((2 * k) % MOD * v[n]) % MOD << '\n';
        i++;
    }
    return 0;
}