题目描述

给定非负整数 $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$。

输出格式

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

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

9
0
2
6
49

3
213467858 78934 30
789432278 948729048 30
114514 1919810 22

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$。

各测试点特殊限制如下：