#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F first
#define S second
 
const int MOD = 1e9 + 7;//XXX
const int C = 26;//XXX
const int XX = 20;
#define ar array

const int MAXN = 1e6 + 10;

int hidden;

int ask(ll x) {
	while(x > 2e7);
	cout << x << endl;
	int r; cin >> r;
	return r;
}

int n, k;

ll add(ar<int,XX> a, ar<int,XX> b) {
	ll s = 0;
	for(int p = 1, i = 0; i < XX && p < 1e9; ++i, p *= k) {
		s += (a[i] + b[i]) % k * p;
	}
	return s;
}

ar<int,XX> get(int x) {
	ar<int,XX> s; s.fill(0);
	for(ll p = 1, i = 0; i < XX && p < 1e9; ++i, p *= k) {
		s[i] = x / p % k;
	}
	return s;
}

ar<int,XX> inv(ar<int,XX> s) {
	for(int i = 0; i < XX; i++) {
		s[i] = (k - s[i]) % k;
	}
	return s;
}

void solve() {
	cin >> n >> k;
	ar<int,XX> s; s.fill(0);
	for(int y = 0; y < n; y += 1) {
		ll now = y % 2 == 0 ? add(s, get(y)) : add(s, inv(get(y)));
		if(ask(now)) {
			cerr << "ALL GOOD\n";
			return;
		}
		// x = y - x;
		s = get(add(get(now), inv(s)));
	}
	assert(0);
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cout << fixed << setprecision(6);
	
	int te = 10;	
	cin >> te;
	for (int w = 1; w <= te; w++){
		//cout << "Case #" << w << ": ";
		solve();
	}
	return 0;
}
