G(kite)

/* Mir Shahriar Sabuj
   CSE 2K10, KUET  */

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <functional>
//#include <conio.h>
using namespace std;

#define LL long long int
#define LI long int
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define PB push_back
#define NL cout << endl
#define PRINT(v) FOR(i, 0, v.size()){ cout <<v[i]<<" "; }NL;
#define FUNC(name,v) name(v.begin(), v.end())
#define CLEAR(v) v.erase(v.begin(), v.end())
#define gcd(a,b)    __gcd(a,b)
#define lcm(a,b) ((a)*((b)/gcd(a,b)))
#define mset(x,with) memset(x,with,sizeof(x))
#define PI 3.141592653589793
#define CASE_print printf("Case %d: ", ++test_case)

int check_bit(int N,int POS){return (N & (1<<POS));}
int on_bit(int N,int POS){return N=N | (1<<POS);}
int off_bit(int N,int POS){return N=N & ~(1<<POS);}
int row[4]={-1,0,0,1};
int col[4]={0,-1,1,0};

////////////////////////////////////////////////////////


const int BUFSIZE = 1 << 16; char BUFFER[BUFSIZE + 5]; int REM = 0, POS = 0;

char GETCHAR()
{if (REM <= 0){POS = 0; REM = fread(BUFFER, 1, BUFSIZE, stdin);
 if (REM <= 0) return EOF;}
 --REM; return BUFFER[POS++];
}

void GETINT(int &VAL)
{
    VAL = 0; char C = EOF; while (C != '-' && !isdigit(C)) C = GETCHAR();
    bool NEG = C == '-'; if (NEG) C = GETCHAR();
    while (isdigit(C)) { VAL = VAL * 10 + C - '0'; C = GETCHAR(); }
    if (NEG) VAL = -VAL;
}


////////////////////////////////////////////////////////////


LL bigmod(LL b, LL e, LL m)
{
    LL r = 1;
    for( ; e; e >>= 1)
    {
        if(e & 1)
          r = (r * b) % m;
        b = b*b % m;
    }
    return r;
}


int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

   int n, test_case=0;
   scanf("%d", &n);


   while(n--)
   {

       CASE_print;

        LL D, V;

       scanf("%lld %lld", &D, &V);

       if(V==0)
       {
           cout << -1;
           NL;
           continue;
       }

       LL A = bigmod(V,  D+1, 1000000007);


       if(D==0)
        cout << V;
       else if(V==1)
       {
        cout << D+1;
       }
       else
         cout << (1-A)/(1-V);

       NL;


   }
}