33OJ
登录 注册

#P17703. [ICPC 2019 Nanjing R] Observation

[ICPC 2019 Nanjing R] Observation

Problem Description

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∈Zd \in \mathbb{Z} as fdf_d.

Now, given a permitted range [L,R][L, R] of viewing distance, a test coefficient KK and a large prime number PP, 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 Format

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

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

Output Format

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