POPCOUNT

음이 아닌 정수 $k$에 대해 $\mathrm{popcount}(k)$는 $k$를 이진법으로 나타냈을 때 나타나는 1의 개수이다.

양의 정수 $A$, $B$, $x$에 대해 $f(x)$를 다음과 같이 정의하자.

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

($a$, $b$는 음이 아닌 정수)

정수 $N$이 주어질 때, $\sum_{i=1}^N f(i)$의 값을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 10000$)

다음 $T$개의 줄에 테스트 케이스가 주어진다. 각 테스트 케이스에는 양의 정수 $N$, $A$, $B$가 공백으로 구분되어 주어진다. ($1 \leq N, A, B \leq 500000$)

각 테스트 케이스에 대해 정답을 한 줄에 하나씩 출력한다. 정답은 64비트 정수 범위를 넘지 않는다.