#include <cstdio>
using namespace std;
const int maxlen=41;

int t,n,k,len,r;
int cnt[maxlen];

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		if (n==1)
		{
			printf("%d\n",0);
			fflush(stdout);
			scanf("%d",&r);
			continue;
		}
		
		len=0;
		for(int tmp=n-1;tmp>0;tmp/=k,len++);
		for(int i=1;i<=len;i++) cnt[i]=0;
		
		for(int i=0;i<n;i++)
		{
			int tmp=i;
			int query=0,base=1;
			for(int j=1;j<=len;j++)
			{
				int now=tmp%k;
				tmp/=k;
				now*=(i&1)?(-1):1;
				now=((now+cnt[j])%k+k)%k;
				cnt[j]=(now-cnt[j])%k;
				query+=base*now;
				base*=k;
			}
			
			printf("%d\n",query);
			fflush(stdout);
			scanf("%d",&r);
			if (r) break;
		}
	}
	return 0;
}

