当前没有测试数据。

题目描述

Given three integers , , . Count the number of pairs $x\ , y$ (with $\leq x \leq A$ and $1 \leq y \leq B$) such that at least one of the following is true:

• (#x\ and\ y$) >
• ($x\ xor\ y$) <

("and", "xor" are bit operators)

输入格式

The first line of the input gives the number of test cases, $T\ (T \leq 100)T$). test cases follow.

For each test case, the only line contains three integers , and . $1 \leq A,B,C \leq 10^9$

输出格式

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

样例

样例输入 1

3
3 4 2
4 5 2
7 8 5

样例输出 1

5
7
31