题目描述

给定正整数 $x,l,r,m$，定义一个长为 $(r-l+1)$ 的序列 $\{a_i\}$，其中 $a_i = (x \oplus (i-l+1)) \bmod m$。

你需要求出 $\{a_i\}$ 中出现次数最多的数出现了多少次。

例如，当 $x=2,l=3,r=7,m=3$ 时，构造出来的序列是 $[1,0,1,1,2]$。因为 $1$ 出现次数最多，出现了 $3$ 次，所以答案为 $3$。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组数据一行四个整数 $x,l,r,m$。

输出格式

对于每组数据，输出一行一个整数，代表该组数据的答案。

3
2 3 7 3
114 514 1919 810
998 244 353 999999

3
2
1

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 200$，$r-l \le 200$；
• 对于另外 $30\%$ 的数据，$m$ 是 $2$ 的整数次幂；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$0 \le x \le 10^9$，$0 \le l \le r \le 10^9$，$2 \le m \le 10^9$。