定义两个数 $x, y$ 的 k-xor 为 $x, y$ 在正整数 $k$ ($k \geq 2$) 进制意义下的不进位加法。现在数学老师有两个整数 $a, b$, 数学老师算出了它们在某个进制 $k$ 下的 k-xor 为 $c$。但在数学老师计算出 $c$ 后，他忘记了 $k$ 的值。你能帮数学老师算出所有大于等于 2 的可能是 $k$ 的不同正整数个数吗？如果有无穷多个满足条件的 $k$，输出 "-1"。

注：两个数在 $k$ 进制下的不进位加法为，将两个数分别写出它们的 $k$ 进制表示，并将两个数对应的位分别相加，然后将每一位相加得到的结果分别对 $k$ 取模，将结果看做一个新的 $k$ 进制数，这个结果即为两个数 $k$ 进制下不进位加法的结果。例如 $16 = (121)_3$ 和 $8 = (022)_3$ 在 3 进制下的不进位加法的结果即为 $(110)_3 = 12$。

输入格式​

第一行包含一个整数 $T$ ($1 \leq T \leq 100$)，表示一共有 $T$ 组测试数据。

每组测试数据包含一行三个整数 $a, b, c(0 \leq a, b, c \leq 10^9)$，表示参与 k-xor 运算的两个数和运算结果。

输出格式

对于每组测试数据，输出一个整数，表示所有大于等于 2 的可能是 $k$ 的不同正整数个数。如果有无穷多个满足条件的 $k$，输出 "-1"。

样例

输入

5
3 5 6
16 8 12
0 0 0
21 21 0
123 456 789

输出

1
2
-1
3
0

数据范围与提示

对于全部测试数据，满足 $1 \leq T \leq 100,0 \leq a,b,c \leq 10^9$