E. Observation
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard 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.

Example
Input
2
1 1 0 11
1 1 1 11
Output
6
7