409242: GYM103466 E Observation

As an astronomer, Alice pilots her spaceship to observe an unknown object in the universe. This object can be viewed as a point in the space in a common theoretical model since its size is significantly smaller than the viewing distance.

Building a space rectangular coordinate system centred at the object, a possible perfect observing position is such which locals at an integral point. Alice records the number of perfect observing positions whose viewing distances are equal to $$$d\in \mathbb{Z}$$$ as $$$f_d$$$.

Now, given a permitted range $$$[L,R]$$$ of viewing distance, a test coefficient $$$K$$$ and a large prime number $$$P$$$, you are asked to calculate $$$\Big(\sum\limits_{d=L}^{R} (f_d\text{ xor } K)\Big)\pmod{P}$$$ to explore the risk factor.

The first line contains an integer $$$T~(1\le T\le 10)$$$ representing the number of test cases.

For each test case, an only line contains four integers $$$L, R, K$$$ and $$$P$$$ described as above, where $$$0\le L\le R\le 10^{13}, 0\le K\le 10^{18}$$$, the prime number $$$P$$$ satisfies $$$P\le 3\times 10^{13}$$$ and $$$R-L+1\le 10^6$$$.

For each test case, print a line which contains an integer representing the risk factor inquired.

2
1 1 0 11
1 1 1 11

6
7