#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
 
const int MOD = 1e9+7;
const ll INF = 1e18;
const int MAXN = 1e6+5;
 
int main() {
    FASTIO
 
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n+1,0), b(n+1,0), c(n+1,0);
        a[2] = (k+1), b[2] = 1, c[2] = (k*k)+k-1;
        for(int i=3; i<=n; i++) {
            a[i] = a[i-1] + c[i-1];
            b[i] = a[i-1];
            c[i] = (k-1)*a[i-1] + (k+1)*b[i-1];
        }
        cout << a[n]+b[n]+c[n] << "\n";
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZBU1RJTyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKdXNpbmcgbGwgPSBsb25nIGxvbmc7Cgpjb25zdCBpbnQgTU9EID0gMWU5Kzc7CmNvbnN0IGxsIElORiA9IDFlMTg7CmNvbnN0IGludCBNQVhOID0gMWU2KzU7CgppbnQgbWFpbigpIHsKICAgIEZBU1RJTwogICAgCiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUodC0tKSB7CiAgICAgICAgaW50IG4sIGs7CiAgICAgICAgY2luID4+IG4gPj4gazsKICAgICAgICB2ZWN0b3I8aW50PiBhKG4rMSwwKSwgYihuKzEsMCksIGMobisxLDApOwogICAgICAgIGFbMl0gPSAoaysxKSwgYlsyXSA9IDEsIGNbMl0gPSAoayprKStrLTE7CiAgICAgICAgZm9yKGludCBpPTM7IGk8PW47IGkrKykgewogICAgICAgICAgICBhW2ldID0gYVtpLTFdICsgY1tpLTFdOwogICAgICAgICAgICBiW2ldID0gYVtpLTFdOwogICAgICAgICAgICBjW2ldID0gKGstMSkqYVtpLTFdICsgKGsrMSkqYltpLTFdOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGFbbl0rYltuXStjW25dIDw8ICJcbiI7CiAgICB9CiAgICAKICAgIHJldHVybiAwOwp9

Mwo3IDEKNyAzCjIwIDE=

3
7 1
7 3
20 1