409242: GYM103466 E Observation

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Observationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$$$.

Output

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

ExampleInput
2
1 1 0 11
1 1 1 11
Output
6
7

加入题单

上一题 下一题 算法标签: