// LUOGU_RID: 98959655
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int n,k;
struct node {
	int a[20];
	node(int x) {
		for(int i=0;i<20;++i) a[i]=0;
		int len=0;
		while(x) {
			a[len]=x%k;
			x/=k,++len;
		}
	}
	node() { node(0); }
	inline int& operator [](int i) { return a[i]; }
	inline friend node operator +(node A,node B) {
		node C;
		for(int i=0;i<20;++i) C[i]=(A[i]+B[i])%k;
		return C;
	}
	inline friend node operator -(node A,node B) {
		node C;
		for(int i=0;i<20;++i) C[i]=(A[i]+k-B[i])%k;
		return C;
	}
	inline int val() {
		int x=0;
		for(int i=0,p=1;i<20;++i,p*=k) {
			if(p>=MAXN) break;
			x+=a[i]*p;
		}
		return x;
	}
};
inline bool read(int x) {
	cout<<x<<endl;
	int ret; cin>>ret; return ret;
}
inline void solve() {
	cin>>n>>k;
	node sum(0);
	for(int i=0;i<n;++i) {
		node q=(i%2==0)?(sum+node(i)):(sum-node(i));
		if(read(q.val())) return ;
		sum=q-sum;
	}
}
signed main() {
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}