#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, k;

int query(int x) {
	printf("%lld\n", x); fflush(stdout);
	int y; scanf("%lld", &y);
	return y;
}

int calc(int x, int y) {
	int res = 0;
	int idx = 0;
	while(x > 0 || y > 0) {
		int xx = x % k;
		int yy = y % k;
		res += (xx - yy + k) % k * pow(k, idx);
		x /= k;
		y /= k;
		idx++;
	}
	return res;
}

void solve() {
	scanf("%lld%lld", &n, &k);
	if(query(0)) return;
	for(int i = 1; i < n; i++) {
		int x;
		if(i & 1) {
			x = query(calc(i - 1, i));
		}
		else {
			x = query(calc(i, i - 1));
		}
		if(x == 1) return;
	}
}

signed main() {
	int t; cin >> t; while(t--)
	solve();
	return 0;
}