77. 位与数对个数

输入格式

第一行数据组数 $T$。

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

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

输出格式

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

3
3 4 2
4 5 2
103 143 88

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\mathrm{\&}2=2$ 不满足位与结果小于 $k=2$ 的条件。