CF2205G Simons and Diophantus Equation

I walk alone, into distance, through the fading light, biding my time for the sunset's final light. — SHUN, [CHAKA](https://open.spotify.com/track/1WL7sDRLAWmMGGJgQMUAGv) Simons has given you two integers $ n $ and $ m $ . Count the number of ordered tuples $ (i, j, k) $ , such that: - $ 0\le i, j, k\le m $ , and - There exist two integers $ x $ and $ y $ , such that $ (i \oplus j) \cdot x + (j \oplus k) \cdot y = n $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The only line contains two integers $ n $ and $ m $ ( $ 1\le n\le 10^9 $ , $ 1\le m\le 3\cdot 10^5 $ ) — the given integers. It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 3\cdot10^5 $ .

For each test case, output a single integer — the number of ordered tuples $ (i,j,k) $ that satisfy the condition.

In the first test case, there are $ 18 $ tuples that satisfy the conditions. For example: - $ (2,1,2) $ is a valid tuple because the equation $ (2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3 $ has an integer solution $ x=3 $ , $ y=-2 $ . - $ (1,1,0) $ is also a valid tuple because the equation $ (1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3 $ has an integer solution $ x=100 $ , $ y=3 $ . - $ (2,0,2) $ is not a valid tuple because the equation $ (2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3 $ has no integer solution. - $ (1,1,1) $ is not a valid tuple because the equation $ (1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3 $ has no integer solution. - $ (3,2,1) $ is not a valid tuple because $ 3 \gt 2 $ .