write a go solution for Description:
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:

- 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 S1010120110011030110100101101001401101001100101100110100110010110ldotsldotsldotsldots

You are given two positive integers n and m. Find the number of positions where the strings S_0S_1ldotsS_m-1 and S_nS_n+1ldotsS_n+m-1 are different.

Input Format:
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<=n,m<=10^18).

Output Format:
For each testcase, output a non-negative integer — the Hamming distance between the two required strings.

Note:
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_0S_1ldotsS_9 is "0110100110", and S_5S_6ldotsS_14 is "0011001011". The Hamming distance between the two strings is 6.. Output only the code with no comments, explanation, or additional text.