cats 的 k-xor

Problem Description

定义两个数 $x,y$ 的 k-xor 为 $x,y$ 在正整数 $k$ $(k\ge 2)$ 进制意义下的不进位加法。现在 cats 有两个整数 $a,b$，cats 算出了它们在某个进制 $k$ 下的 k-xor 为 $c$。但在 cats 计算出 $c$ 后，cats 忘记了 $k$ 的值。你能帮 cats 算出所有大于等于 $2$ 的可能是 $k$ 的不同正整数个数吗？如果有无穷多个满足条件的 $k$，输出 $-1$。 注：两个数在 $k$ 进制下的不进位加法为，将两个数分别写出它们的 $k$ 进制表示，并将两个数对应的位分别相加，然后将每一位相加得到的结果分别对 $k$ 取模，将结果看做一个新的 $k$ 进制数，这个结果即为两个数 $k$ 进制下不进位加法的结果。例如 $16 = (121)_3$ 和 $8 = (022)_3$ 在 $3$ 进制下的不进位加法的结果即为 $(110)_3 = 12$。

Input

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

Output

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

Sample Input

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

Sample Output

1
2
-1
3
0

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）