本题可以看成是原题的一个加强版，原题中的$P$是一个质数，本题并没有这一限制。

题目描述

给定两个整数$P,m$，计算有多少个非负整数$g$，满足 $g\le m$ 并且下面的式子成立：

其中 $⊕$ 代表异或(XOR)

输入格式

第一行一个整数 $T(1\le T\le10^5)$ 代表测试数据数量。

接下来 $T$ 行，每行两个整数$P,m(2\le P \le 10^{18},0\le m\le10^{18})$。

输出格式

输出 $T$ 行，一行一个答案

样例

3
2 0
7 11
1145141 998244353

1
2
872