P17703 [ICPC 2019 Nanjing R] Observation

作为天文学家，Alice 驾驶她的宇宙飞船去观察宇宙中的一个未知物体。在通常的理论模型中，由于该物体的大小显著小于观察距离，它可以被视为空间中的一个点。 以该物体为中心建立一个空间直角坐标系，一个可能的完美观察位置是位于整点处的位置。Alice 将观察距离等于 $d \in \mathbb{Z}$ 的完美观察位置的数量记为 $f_d$。 现在，给定一个允许的观察距离范围 $[L, R]$、一个测试系数 $K$ 以及一个大素数 $P$，请你计算 $\Big(\sum\limits_{d=L}^{R} (f_d \text{ xor } K)\Big) \pmod{P}$ 以探索风险因子。

第一行包含一个整数 $T$ $(1 \le T \le 10)$，表示测试数据的组数。 对于每组测试数据，仅有一行包含四个整数 $L, R, K$ 和 $P$，意义如上所述，其中 $0 \le L \le R \le 10^{13}$，$0 \le K \le 10^{18}$，素数 $P$ 满足 $P \le 3 \times 10^{13}$ 且 $R - L + 1 \le 10^6$。

对于每组测试数据，输出一行一个整数，表示所求的风险因子。

翻译由 DeepSeek V4 Pro 完成