3019: 超级计算姬

“奋战三星期，造台计算机”。小Y响应号召，花了三个月造了台超级计算姬。

超级计算姬比普通计算机高到不知道哪里去了。运行起来跑的比谁都快，还能和人谈笑风生。真是“水能载舟，亦可赛艇”。

超级计算姬喜欢与人比智商，他抛出了几个问题给小 Y 来测试他的智商：

1 给定正整数 a, b, c，求方程 a∗x ≡ b (mod c) 的最小非负整数解。

2 给定正整数 f, g, h，求方程 g^x ≡ f (mod h) 的最小非负整数解。

3 给定正整数 u, v, w，求方程 x^u ≡ v (mod w) 在模 w 意义下解的数量 及最小非负整数解。

4 给定正整数 x, y, z，求 (φ(x) + µ(y)) mod z 的值。其中 φ(x) 是欧拉 函数，µ(y) 是莫比乌斯函数。 小 Y 只会做第三问的后一个问题，你的智商能帮他解决其他问题吗？

输入文件共四行，按上述描述中四个问题的顺序，给出每个问题。

第一行三个正整数 a, b, c 表示第一个问题，保证 a, b < c

第二行三个正整数 f, g, h 表示第二个问题，保证 f, g < h。

第三行三个正整数 u, v, w 表示第三个问题，保证 w 为质数且 u, v < w。

第四行三个正整数 x, y, z 表示第四个问题

共四行每行一个整数，分别表示四个问题的答案。

对于前两个问题，若问题无解则输出-1。

对于第三个问题你只需输出解的数量。

3 6 8
9 10 12
4 4 7
5 4 20

2
-1
2
4