sng summer camp 5

C. 位与数对个数

单点时限: 2.5 sec

内存限制: 256 MB

给定三个整数 $a,b,k$,计算满足 $x$ ($0 \le x < a$) 和 $y$ $(0 \le y < b)$ 的位与结果小于 $k$(即 $0 \le x \& y < k$)的有序数对 $(x,y)$ 的个数。

输入格式

第一行数据组数 $T$。

接下来 $T$ 行,每行三个正整数 $a,b,k$。

  • 数据点 1: 占 $30\%$, $1 \le T \le 100$, $a,b,k \le 100$;
  • 数据点 2: 占 $40\%$, $1 \le T \le 10^5$, $a,b,k \le 100$;
  • 数据点 3: 占 $30\%$, $1 \le T \le 10^5$, $a,b,k \le 10^9$.

输出格式

对于每组数据输出数对个数。

样例

Input
3
3 4 2
4 5 2
103 143 88
Output
10
16
14377

提示

$a=3,b=4,k=2$ 时,满足条件的数对有 $(0,0)$, $(0,1)$, $(0,2)$, $(0,3)$, $(1,0)$, $(1,1)$, $(1,2)$, $(1,3)$, $(2,0)$, $(2,1)$。总计是 $10$ 对。注意:$(0,1)$ 和 $(1,0)$ 是两对不同的数对。$(2,2)$ 不满足条件,因为 $2 \& 2=2$ 不满足位与结果小于 $k=2$ 的条件。