作为一名天文学家，Alice 驾驶着她的宇宙飞船去观测宇宙中的一个未知天体。在一个通用的理论模型中，由于该天体的大小远小于观测距离，它可以被视为空间中的一个点。

建立一个以该天体为中心的空间直角坐标系，一个理想的观测位置是指位于整点坐标上的位置。Alice 记录了观测距离等于 $d \in \mathbb{Z}$ 的理想观测位置的数量，记为 $f_d$。

现在，给定观测距离的允许范围 $[L, R]$、一个测试系数 $K$ 以及一个大素数 $P$，请你计算 $\left( \sum_{d=L}^{R} (f_d \oplus K) \right) \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$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示所求的风险因子。

样例

输入 1

2
1 1 0 11
1 1 1 11

输出 1

6
7