Div3F

#include <bits/stdc++.h>
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define NeedForSpeed                  \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
#define f first
#define s second
const int mod = 1000000007;

int findXOR(int n)
{
    int mod = n % 4;
    if (mod == 0)
        return n;
    else if (mod == 1)
        return 1;
    else if (mod == 2)
        return n + 1;
    else
        return 0;
}

int findXOR(int l, int r)
{
    return findXOR(l - 1) ^ findXOR(r);
}

void solve()
{
    int l, r, i, k;
    cin >> l >> r >> i >> k;
    if (i == 0)
    {
        cout << 0 << endl;
        return;
    }
    int step = 1LL << i;
    int leftmod = l % (1LL << i);
    int firstocc = l + (k - leftmod);
    if (firstocc < l)
    {
        firstocc += (1LL << i);
    }
    int rightmod = r % (1LL << i);
    int lastocc = r + (k - rightmod);
    if (lastocc > r)
    {
        lastocc -= (1LL << i);
    }
    // edge case when only 1 element occurs in the range
    if (firstocc > r || lastocc < l)
    {
        if ((firstocc != lastocc))
        {
            cout << ((findXOR(l - 1) ^ findXOR(r))) << endl;
            return;
        }
        else
        {
            cout << ((findXOR(l - 1) ^ findXOR(r)) ^ k) << endl;
            return;
        }
    }
    int start = 0;
    if (l - k > 0)
    {
        start = ((l - k) + step - 1) / step;
    }
    int end = max(0LL, (r - k) / step);
    int XOR = (findXOR(start - 1) ^ findXOR(end)) << i;
    if ((end - start + 1) % 2 == 1)
    {
        XOR ^= k;
    }
    cout << (findXOR(l - 1) ^ findXOR(r) ^ XOR) << endl;
}

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