问题 F: cats 的 k-xor

内存限制:512 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

定义两个数 x, y 的 k-xor 为 x, y 在正整数 k (k ≥ 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


				

输入格式

第一行包含一个整数 T (1 ≤ T ≤ 100),表示一共有 T 组测试数据。 
每组测试数据包含一行三个整数 a, b, c(0 ≤ a, b, c ≤ 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