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:

Iteration

$S$ before iteration

$S$ before iteration with flipped bits

Concatenated $S$

1

0

1

01

2

01

10

0110

3

0110

1001

01101001

4

01101001

10010110

0110100110010110

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


-----Input-----

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


-----Output-----

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


-----Examples-----

Input
6
1 1
5 10
34 211
73 34
19124639 56348772
12073412269 96221437021
Output
1
6
95
20
28208137
48102976088


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

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Bit manipulation

Divide and conquer

Mathematics


Solutions:
import random
cache = {}

def popcount(n):
	res = 0
	while n:
		res += 1
		n &= n - 1
	return res

def solve(n, k):
	if k == 0:
		return 0
	if k == 1:
		return popcount(n) & 1
	if k % 2 == 1:
		t = solve(n, k - 1)
		x = popcount(k - 1 ^ n + k - 1) & 1
		return t + x
	if (n, k) in cache:
		return cache[n, k]
	if n % 2 == 0:
		one_cell = 2
		zero_cell = 0
		cnt1 = solve(n // 2, k // 2)
		cnt0 = k // 2 - cnt1
	else:
		one_cell = 0
		zero_cell = 1
		cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
		cnt0 = k - cnt1
	res = one_cell * cnt1 + zero_cell * cnt0
	cache[n, k] = res
	return res
t = int(input())
for _ in range(t):
	cache.clear()
	(n, k) = map(int, input().split())
	print(solve(n, k))