P13953 [ICPC 2023 Nanjing R] Primitive Root

BaoBao has just learnt about primitive roots in number theory and is showing off his knowledge to Little Cyan Fish through an instant messaging software. :::align{center}  This image is only for amusement and has nothing to do with the problem itself. You can safely skip this image if you can't read Chinese. ::: Based on the fact that if a non-negative integer $g$ is a primitive root modulo $P$ (where $P$ is a prime), then $g^{P - 1} \equiv 1 \pmod{P}$, BaoBao decided to use the expression $\texttt{(g \^ (P - 1)) \% P == 1}$ to check if $g$ is a primitive root modulo $P$. Unfortunately, in most programming languages (for example C and C++), $\texttt{\^ }$ is the bitwise exclusive-or (XOR) operator, not the power operator. Little Cyan Fish spotted this issue at once and now he is interested in the following problem: Given a prime number $P$ and a non-negative integer $m$, how many non-negative integers $g$ satisfies $g \leq m$ and $g \oplus (P-1) \equiv 1 \pmod{P}$? Here $\oplus$ is bitwise exclusive-or (XOR) operator. Please help Little Cyan Fish solve this problem.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 10^{5}$) indicating the number of test cases. For each test case: The first and only line contains two integers $P$ and $m$ ($2 \le P \le 10^{18}$, $0 \leq m \leq 10^{18}$, $P$ is a prime).

For each test case, output one line containing one integer indicating the number of $g$ satisfying the constraints.