package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

type Cnt [2][2]uint64

func lowerDistribution(k int, r uint64) Cnt {
	var dp Cnt
	dp[0][0] = 1
	for pos := 0; pos < k; pos++ {
		bit := (r >> uint(pos)) & 1
		var ndp Cnt
		for c := 0; c <= 1; c++ {
			for p := 0; p <= 1; p++ {
				v := dp[c][p]
				if v == 0 {
					continue
				}
				// i_bit = 0
				s := uint64(c) + bit
				co := s >> 1
				np := p ^ int(co)
				ndp[co][np] += v
				// i_bit = 1
				s = uint64(c) + bit + 1
				co = s >> 1
				np = p ^ int(co)
				ndp[co][np] += v
			}
		}
		dp = ndp
	}
	return dp
}

func tailParity(nh, ah, carry uint64) uint64 {
	var parity uint64 = 0
	for nh != 0 || ah != 0 {
		s := (nh & 1) + (ah & 1) + carry
		if s >= 2 {
			carry = 1
			parity ^= 1
		} else {
			carry = 0
		}
		nh >>= 1
		ah >>= 1
	}
	return parity
}

func hammingDistance(n, m uint64) uint64 {
	if m == 0 {
		return 0
	}
	var totalOdd uint64 = 0
	a := uint64(0)
	rem := m
	cache := make(map[int]Cnt)
	for rem > 0 {
		var L uint64
		if a == 0 {
			shift := 63 - bits.LeadingZeros64(rem)
			L = 1 << uint(shift)
		} else {
			lb := a & -a
			for lb > rem {
				lb >>= 1
			}
			L = lb
		}
		k := bits.TrailingZeros64(L)
		cnt, ok := cache[k]
		if !ok {
			r := n & (L - 1)
			cnt = lowerDistribution(k, r)
			cache[k] = cnt
		}
		nh := n >> uint(k)
		ah := a >> uint(k)
		t0 := tailParity(nh, ah, 0)
		t1 := tailParity(nh, ah, 1)
		var blockOdd uint64
		if t0 == 0 {
			blockOdd += cnt[0][1]
		} else {
			blockOdd += cnt[0][0]
		}
		if t1 == 0 {
			blockOdd += cnt[1][1]
		} else {
			blockOdd += cnt[1][0]
		}
		totalOdd += blockOdd
		a += L
		rem -= L
	}
	if (bits.OnesCount64(n) & 1) == 0 {
		return totalOdd
	}
	return m - totalOdd
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}
	for ; t > 0; t-- {
		var n, m uint64
		fmt.Fscan(in, &n, &m)
		ans := hammingDistance(n, m)
		fmt.Fprintln(out, ans)
	}
}