#include <iostream>
#define print(var) cout << #var << " " << var << endl;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int tests;
    cin >> tests;
        unsigned long long x, y, z, n;
    while (tests--) {
        cin >> x >> y >> z >> n;
        print(x);
        print(y);
        print(z);
        print(n);
        n--;
        n%=20000;
        print(n);
        unsigned counter = 0;
        int lastResult = x;
        int result;

        while(counter < n) {
            result = (y*lastResult + z) % 20000;
            lastResult = result;
            counter ++;
            print(result);
        }

        if(n==0) {
            result = (y*lastResult + z) % 20000;
        }

        cout << result << endl;
    }
    return 0;
}