#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll bitmodsub(ll a, ll b, ll k)
{
    ll ans = 0, cur = 1;
    while (a || b)
    {
        ll t = (a % k - b % k + k) % k;
        a /= k, b /= k;
        ans += (t * cur);
        cur *= k;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n, k, r;
        cin >> n >> k;
        cout << 0 << endl;
        cin >> r;
        ll cnt = 1;
        while (!r)
        {
            if (cnt & 1)
                cout << bitmodsub(cnt - 1, cnt, k) << endl;
            else
                cout << bitmodsub(cnt, cnt - 1, k) << endl;
            cnt++;
            cin >> r;
        }
    }
}