B'Let 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: For example, here are the first four iterations: 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. Each test contains multiple test cases. The first line of the input contains a single integer t ( 1 <= t <= 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 <= q n,m <= q 10^{18} ). For each testcase, output a non-negative integer -- the Hamming distance between the two required strings. The 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 . '...