#include <iostream>

using namespace std;

typedef long long ll;

ll calculateXor(int a, int b, int k) {	
	ll number = 0;
	ll degree = 1;
	while (a > 0 || b > 0) {
		int coeff = (a % k + b % k) % k;
		number += coeff * degree;
		b /= k;
		a /= k;
		degree *= k;
	}
	
	return number;
}

ll inverse(int a, int k) {
	ll number = 0;
	ll degree = 1;
	while (a > 0) {
		int coeff = (k - a % k) % k;
		number = number + degree * coeff;
		a /= k;
		degree *= k;
	}
	return number;
}

void solve() {
	int n, k;
	cin >> n >> k;
	cout << 0 << endl;
	cout.flush();
	int r;
	cin >> r;
	if (r)
		return;

	// X = calculateXor(0, inverse(X, k), k);
	// cout << "newX = " << X << endl;
	for (int i = 1; i < n; i++) {
		int possiblePassword = 0;
		if (i % 2) {
			possiblePassword = calculateXor(i - 1, inverse(i, k), k);
		} else {
			possiblePassword = calculateXor(i, inverse(i - 1, k), k);
		}
		cout << possiblePassword << endl;
		cout.flush();
		int r;
		cin >> r;
		if (r) {
			return;
		}

		// X = calculateXor(possiblePassword, inverse(X, k), k);
		// cout << "newX = " << X << endl;
		// history = calculateXor(history, possiblePassword, k);
	}

	// cout << "Bad\n";
}


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


	return 0;
}
