Cengiz 最近学习了斐波那契数,现在他正在研究不同的算法来找到它们。在厌倦了阅读这些数字后,他带来了自己的新型数字,并将其命名为 XORinacci 数字。他将它们定义如下:
- $$$f(0) = a$$$;
- $$$f(1) = b$$$;
- $$$f(n) = f(n-1) \oplus f(n-2)$$$ 当 $$$n > 1$$$ 时,其中 $$$\oplus$$$ 表示按位异或运算。
给你三个整数$$$a$$$、$$$b$$$和$$$n$$$,计算$$$f(n)$$$。
您必须回答 $$$T$$$ 独立测试用例。
输入
输入包含一个或多个独立的测试用例。
输入的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^3$$$),即测试用例的数量。
$$$T$$$ 以下各行分别包含三个空格分隔的整数 $$$a$$$、$$$b$$$ 和 $$$n$$$ ($$$0 \le a, b, n \le 10^9$$$)。
输出
对于每个测试用例,输出$$$f(n)$$$。
示例
输入 #1
3 3 4 2 4 5 0 325 265 1231232
输出 #1
7 4 76
注意
在第一个示例中,$$$f(2) = f(0) \oplus f(1) = 3 \oplus 4 = 7$$$。