F. Zeros and Onestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet S be the Thue-Morse sequence. In other words, S is the 0-indexed binary string with infinite length that can be constructed as follows:   Initially, let S be "0".  Then, we perform the following operation infinitely many times: concatenate S with a copy of itself with flipped bits.For example, here are the first four iterations:  IterationS before iterationS before iteration with flipped bitsConcatenated S1010120110011030110100101101001401101001100101100110100110010110\ldots\ldots\ldots\ldots  You are given two positive integers n and m. Find the number of positions where the strings S_0 S_1 \ldots S_{m-1} and S_n S_{n + 1} \ldots S_{n + m - 1} are different. InputEach test contains multiple test cases. The first line of the input contains a single integer t (1 \le t \le 100) — the number of test cases. The description of the test cases follows.The first and only line of each test case contains two positive integers, n and m respectively (1 \leq n,m \leq 10^{18}).OutputFor each testcase, output a non-negative integer — the Hamming distance between the two required strings.ExampleInput
61 15 1034 21173 3419124639 5634877212073412269 96221437021Output
1
6
95
20
28208137
48102976088
NoteThe string S is equal to 0110100110010110....In the first test case, S_0 is "0", and S_1 is "1". The Hamming distance between the two strings is 1.In the second test case, S_0 S_1 \ldots S_9 is "0110100110", and S_5 S_6 \ldots S_{14} is "0011001011". The Hamming distance between the two strings is 6.
61 15 1034 21173 3419124639 5634877212073412269 96221437021
1 6 95 20 28208137 48102976088 
['bitmasks', 'divide and conquer', 'dp', 'math', '*2500']