该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Yet Another 模拟

题目描述

好数：对于数 $x$ 分解质因数，表示为 $x=p_1^{c_1}\times p_2^{c_2}\times\cdots p_{len}^{c_{len}}$ ($p_i$ 为质数)。若 $\max\limits^{len}_{i=1}c_{i}\le1$，则称 $x$ 为好数。值得注意的是，$1$ 也是好数。

询问若干区间内好数的和的异或结果。

输入格式

第一行一个整数 $T$，表示询问组数。

第二行五个整数 $L, R, a, b, c$ 表示第一个询问的范围为 $[L, R]$，对于第 $i(i > 1)$ 个询问，该次询问的范围 $L, R$ 与上次询问的范围 $L_0$, $R_0$ 满足如下关系：

设 $x = ((L_0 ⊕ b)+a)\mod c+1$，$y = ((R_0 ⊕ b)+a)\mod c+1$，则 $L = \min(x, y), R = \max(x, y)$。

其中 $⊕$ 表示二进制下按位异或运算。

输出格式

设第 $i$ 次询问的答案为 $ans_i$，则你需要输出 $ans_1⊕ans_2⊕\cdots⊕ans_T$。

样例 #1

样例输入 #1

2
2 9 1 0 20

样例输出 #1

48

样例 #2

样例输入 #2

2
20 90 10 6 20

样例输出 #2

2387

样例 #3

样例输入 #3

2
200 900 100 6 200

样例输出 #3

241632

提示

对于第一次询问，满足条件的好数有 $2,3,5,6,7$，和为 $23$。

对于第二次询问：

$x = ((2 ⊕ 0)+1)\mod 20+1=4$

$y = ((9 ⊕ 0)+1)\mod 20+1=11$

则询问的范围是 $[4,11]$，满足条件的好数有 $5,6,7,10,11$，和为 $39$。

两次询问答案的异或和为 $23⊕39=48$。

【数据范围】

$1 \le L,R,c,T \le 10^7$

$1 \le a,b \le 10^9$

数据点	$l,r,c\le$	$T$
$1$	$100$	$100$
$2,3$		$10^6$
$4,5$	$10^5$
$6-10$	$10^6$	$10^7$
$11$	$10^7$

本题通过前 $10$ 个点即可获得满分，第 $11$ 个点作为附加分出现，共 $1$ 分。