//#include <bits/stdc++.h>
//#define int long long int
//#define double long double
//#define endl '\n'
//#define all(c) c.begin(),c.end()
//#define mp(x,y) make_pair(x,y)
//#define eb emplace_back
//#define tr(k,st,en) for(int k = st; k <= en ; k++)
//#define trb(k,en,st) for(int k = en; k >= st ; k--)
//#define test int TN; cin>>TN; tr(T,1,TN)
//#define mxe(c) max_element(all(c))
//#define mne(c) min_element(all(c))
//using namespace std;
//
//template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
//template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
//
//void dbg_out() { cerr << endl; }
//template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
//
//#ifdef LOCAL
//#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
//#else
//#define dbg(...)
//#endif
//
//typedef pair<int, int> pr;
//typedef vector<int> vi;
//typedef vector<vi> vvi;
//typedef vector<pr> vpr;
//
////const int mod = 1e9+7;
////const int inf = 9e18;
//
//double func(double c, double m, double p, double v) {
//    if(c <= 0.0000000000001 and m <= 0.0000000000001) return 1;
//    double ret = 0;
//    if(c > 0.0000000000001) {
//    if(c <= v + 0.00000000001) {
//        double de = (c/2.0);
//        ret += c * (func(0, m + de, p+de, v) + 1);
//    } else {
//        double de = ((v - c)/2.0);
//        ret += c * (func(v, m + de, p+de, v) + 1);
//    }
//    }
//    if(m > 0.0000000000001){
//    if(m <= v + 0.00000000001) {
//        double de = (m/2.0);
//        ret += m * (func(c + de, 0 , p+de, v) + 1);
//    } else {
//        double de = ((v - m)/2.0);
//        ret += m * (func(c + de, v, p+de, v) + 1);
//    }
//    }
//    return ret;
//}
//
//int32_t main(){
//    std::ios::sync_with_stdio(false);
//    cin.tie(NULL); cout.tie(NULL);
////    cout<<"----START-----"<<endl;
//    test{
//        double a,b,c,d;
//        cin>>a>>b>>c>>d;
//        cout<<func(a, b, c, d)<<endl;
//    }
//    return 0;
//}

#include <bits/stdc++.h>
#define int long long int
#define double long double
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define eb emplace_back
#define tr(k,st,en) for(int k = st; k <= en ; k++)
#define trb(k,en,st) for(int k = en; k >= st ; k--)
#define test int TN; cin>>TN; tr(T,1,TN)
#define mxe(c) max_element(all(c))
#define mne(c) min_element(all(c))
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

typedef pair<int, int> pr;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pr> vpr;

//const int mod = 1e9+7;
//const int inf = 9e18;

int k;
int sub(int a, int b) {
    vector<int> t1, t2;
    while(a > 0 ) {
        t1.eb(a%k);
        a/=k;
    }
    while(b > 0) {
        t2.eb(b%k);
        b/=k;
    }
    while(t2.size() < t1.size()) {
        t2.eb(0);
    }
    while(t1.size() < t2.size()) {
        t1.eb(0);
    }
    int ret = 0;
    int x = 1;
    vector<int> tm;
    for(int i=0;i<t2.size();i++) {
        tm.eb((t1[i] - t2[i] + k)%k);
    }
    for(int i=0;i<t2.size();i++) {
        ret += tm[i] * x;
        x *= k;
    }
    return ret;
}

int add(int a, int b) {
    vector<int> t1, t2;
    while(a > 0 ) {
        t1.eb(a%k);
        a/=k;
    }
    while(b > 0) {
        t2.eb(b%k);
        b/=k;
    }
    if(t1.size() < t2.size()) {
        swap(t1, t2);
    }
    while(t2.size() < t1.size()) {
        t2.eb(0);
    }
    int ret = 0;
    int x = 1;
    vector<int> tm;
    for(int i=0;i<t2.size();i++) {
        tm.eb((t2[i] + t1[i])%k);
    }
    for(int i=0;i<t2.size();i++) {
        ret += tm[i] * x;
        x *= k;
    }
    return ret;
}


void solve(){
    int n;
    cin>>n>>k;
    int x=0;
    tr(i,0,n-1){
        int orig=i;
        int toask= i%2 == 0 ? add(x, orig) : sub(x, orig);
        cout<<toask<<endl;
        int r;
        cin>>r;
        if(r==1) return;
        x = sub(toask, x);
    }
}
int32_t main(){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    cout<<"----START-----"<<endl;
    test{
        solve();
    }
    return 0;
}
