P17703 [ICPC 2019 Nanjing R] 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.