#P10001. cats 的 k-xor

    ID: 8223 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 4 上传者: 标签>CF1400普及约数成对枚举进位制转换直接模拟2024“钉耙编程”中国大学生算法设计超级联赛(8)

cats 的 k-xor

cats 的 k-xor

Problem Description

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

Input

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

Output

对于每组测试数据,输出一个整数,表示所有大于等于 22 的可能是 kk 的不同正整数个数。如果有无穷多个满足条件的 kk,输出 −1-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)