#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define PI pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define random(a,b) (mtrand()%(b-a+1)+a)
#define PLI pair<ll,int>
#define lc ch[x][0]
#define rc ch[x][1]
#define D(x) #x,x
#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
void debug() {}
template<class T,class ...U> void debug(const T &head,const U &... tail)
{
    cerr<<head<<(sizeof...(tail)?" ":"\n"),debug(tail...);
}
const int mx=2e5+10;
const ll mod=1e9+7;
mt19937_64 mtrand(time(0));
int n,m,T;
int ask(int x)
{
    cout<<x<<"\n";
    cout.flush();
    cin>>x;
    return x;
}
int ans[mx],cnt;
ll cm[mx];
int solve(int x)
{
    int res=0;
    if (x&1)
    {
        for (int i=0;i<cnt;++i)
        {
            res=res+((ans[i]-x%m)%m+m)%m*cm[i];
            x/=m;
        }
    }
    else
    {
        for (int i=0;i<cnt;++i)
        {
            res=res+(ans[i]+x%m)%m*cm[i];
            x/=m;
        }
    }
    return res;
}
int main()
{
    FIO;
    cin>>T;
    while (T--)
    {
        cin>>n>>m;
        ll tt=n-1;
        cnt=0;
        while (tt)
        {
            ++cnt;
            tt/=m;
        }
        cm[0]=1;
        ans[0]=0;
        for (int i=1;i<cnt;++i) ans[i]=0,cm[i]=cm[i-1]*m;
        for (int i=0;i<n;++i)
        {
            int now=solve(i);
            if (ask(now)) break;
            for (int j=0;j<cnt;++j)
            {
                ans[j]=((now%m-ans[j])%m+m)%m;
                now/=m;
            }
        }
    }
}
