CF1734F Zeros and Ones

Let $ S $ be the [Thue-Morse sequence](https://en.wikipedia.org/wiki/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: Iteration $ S $ before iteration $ S $ before iteration with flipped bitsConcatenated $ S $ 1010120110011030110100101101001401101001100101100110100110010110 $ \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.

Each 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} $ ).

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 $ .