題目描述

你是小明，你被要求制造一个机器：

它有三个功能

1.输入a,b,c, 输出a^b mod c 的值

2.输入a,b,c, 输出最小非负整数x, 满足 ax ≡ b ( mod c )

3.输入a,b,c, 输出最小非负整数x, 满足 a^x ≡ b ( mod c )

请你满足老板的需求

輸入格式

输入两个正整数N,M, 表示有接下来有的询问个数和要使用的功能

以下 N 行每行包含三个正整数 a,b,c，描述一个询问。

输出包括N行，对于每个询问各输出一个答案
如果M=2,3 找不到答案，输出 None .

["3 1\r\n2 1 3\r\n2 2 3\r\n2 3 3","4 3\r\n2 1 3\r\n2 2 3\r\n2 3 3\r\n2 4 3"]

["2\r\n1\r\n2","0\r\n1\r\nNone\r\n0"]

所有数据均满足：1≤a,b,c≤10⁹，c 是质数，1≤N≤10。

会定时新增测支