### 问题描述 大衣最近在研究与和或，他定义一个函数 $F(P,Q,R)=(R|P)-(Q$&$P)$。 其中 `|` 表示二进制按位或，`&` 表示二进制按位与。 大衣有三个非负整数 $A,B,C​$，他想计算满足下列条件的整数 $X​$ 的数量： - $0\le X\le 2^C$。 - $F(X,A,B)​$ 是满足 $X​$ 取值条件下最大的可能值。 ### 输入格式 第一行输入一个正整数 $T$ 表示测试数据的组数。 接下来 $T$ 行每行输入三个整数 $A,B,C$。 ### 输出格式 输出一个整数表示满足条件的整数 $X$ 的数量。 ### 样例输入1 ```text 3 1 2 3 0 0 2 87 986 15 ``` ### 样例输出1 ```text 4 1 64 ``` ### 说明 - 样例 $1$：有 $4$ 个可能的 $X$ 值能使 $F(X,A,B)$ 到达最大，它们是 $4,5,6,7$，此时 $F(X,A,B)=5$。 - 样例 $2​$：仅有 $1​$ 个可能的 $X​$ 值能使 $F(X,A,B)​$ 到达最大，它是 $3​$，此时 $F(3,0,0)=3​$。 ### 评测数据规模 对于所有的评测数据，$1\le T\le 10^4$，$0\le C\le 30$，$0\le A,B<2^C$。