Sum and Xor

Let $F(s, x)$ be the number of triplets of nonnegative integers whose sum is $s$ and bitwise xor is $x$. Given $a$, $b$, and $N$, find the sum of $F(a \cdot n, b \cdot n)$ for all $n$ such that $1 \leq n \leq N$. ### Input The first line of input contains an integer $T$ denoting the number of test cases. The description of $T$ test cases follows. Each test case consists of a single line contain