1 #include<cstdio>
 2 #include<cstring>
 3 bool b[500005];
 4 int  a[500005];
 5 int main()
 6 {
 7     long long z, m, l;
 8     int n, T;
 9     scanf("%d", &T);
10     while (T--)
11     {
12         scanf("%d%lld%lld%lld", &n, &m, &z, &l);
13         int j, f, L, i;
14         memset(b, 0, sizeof(b));
15         L = 0;
16         b[0] = true;
17         a[0] = 0;
18         for (j = 1;; j++)
19         {
20             L = (m*L + z) % l;//随机数产生函数，会有循环出现
21             if (b[L] == true) break;
22             b[L] = true;
23             a[j] = L;
24         }
25         int sum = 0;
26         for (f = 0; f < j; f++)
27         {
28             if (a[f] == L) break;
29             sum = sum ^ (a[f] << 1);
30         }
31         int cycle = j - f;
32         int div = (n - f) / cycle;
33         int mod = (n - f) % cycle;
34         if (div & 1)
35         {
36             for (i = f + mod; i < j; i++)
37                 sum = sum ^ (a[i] << 1);
38         }
39         else
40         {
41             for (i = f; i < f + mod; i++)
42                 sum = sum ^ (a[i] << 1);
43         }
44         printf("%d\n", sum);
45     }
46 }