题目描述

给定非负整数 $x, y, h$，保证 $0 \le x, y < 2^h$，你需要找到一个整数 $z$ 使得 $0\le z<2^h$ 且 $(x\oplus z)\times(y\oplus z)$ 最大，求这个最大值。

其中 $\oplus$ 表示按位异或运算。

输入格式

本题输入包含多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 仅一行，三个整数 $x, y, h$。

输出格式

对于每组数据，输出一行一个数，表示答案。

输入输出样例 #1

输入 #1

5
0 0 2
1 0 1
0 3 2
1 0 2
3 3 3

输出 #1

9
0
2
6
49

输入输出样例 #2

输入 #2

3
213467858 78934 30
789432278 948729048 30
114514 1919810 22

输出 #2

934398046840059525
763270444894761743
10523686794257

说明/提示

【样例解释 #1】

每一组数据分别可能选取的 $z$ 为 $3,0,1,2,4$。

【数据范围】

对于所有数据，保证 $1\le T\le 10^6$，$0\le x,y<2^h$，$1\le h\le 30$。

各测试点特殊限制如下：