POPCOUNT

For a nonnegative integer $k$, $\mathrm{popcount}(k)$ is the number of 1s in the binary representation of $k$.

For positive integers $A$, $B$, and $x$, define $f(x)$ as follows.

$f(x)=\max_{a+b=x}\{A\times \mathrm{popcount}(a) + B\times \mathrm{popcount}(b)\}$

($a$ and $b$ are nonnegative integers)

Given an integer $N$, find the value of $\sum_{i=1}^N f(i)$.

The first line contains the number of test cases $T$. ($1 \leq T \leq 10000$)

Each of the next $T$ lines contains a test case, given as three positive integers $N$, $A$, and $B$ separated by spaces. ($1 \leq N, A, B \leq 500000$)

For each test case, print the answer on its own line. The answer does not exceed the range of a 64-bit integer.