题目描述

堡堡刚刚学会了数论中的原根。现在他正通过即时通信软件向小青鱼炫耀他的知识。

:::align{center}

本图仅为娱乐，与题目本身无关。如果您看不懂中文，可以安全地跳过本图。 :::

因为如果非负整数 $g$ 是模 $P$ 的原根（$P$ 是质数），则 $g^{P - 1} \equiv 1 \pmod{P}$，所以堡堡打算用表达式 $\texttt{(g \^ (P - 1)) \% P == 1}$ 来检查 $g$ 是不是模 $P$ 的原根。不幸的是，在大多数编程语言中（例如 C 和 C++）， $\texttt{\^ }$ 是按位异或（XOR）运算符，而不是次方运算符。小青鱼一下子就发现了这个错误，现在他开始思考起以下问题：

给定质数 $P$ 和非负整数 $m$，有多少非负整数 $g$ 满足 $g \leq m$ 且 $g \oplus (P-1) \equiv 1 \pmod{P}$？这里 $\oplus$ 是按位异或（XOR）运算符。

请帮助小青鱼解决这个问题。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 10^{5}$）表示测试数据组数，对于每组测试数据：

第一行输入两个整数 $P$ 和 $m$（$2 \le P \le 10^{18}$，$0 \leq m \leq 10^{18}$，$P$ 是质数）。

输出格式

每组数据输出一行一个整数表示满足限制的 $g$ 的数量。

3
2 0
7 11
1145141 998244353

1
2
872