总所周知，莱昂哈德·欧拉（Leonhard Euler %%%）是一个数学大佬，对数学、力学、几何学等等有着非常突出的贡献。我们可以在各种地方看到各种的欧拉公式，欧拉定理，欧拉函数，欧拉回路...

总所不周知，繁凡さん很喜欢翻论文，翻各种奇怪的博客，学各种奇怪的算法。有一天，他在划水的时候发现了一个有趣的论文：

“看到让欧拉出丑，我啪的一下就点进去了，很快啊。”

嗷，原来是昨天（18世纪），有几个年轻人，他们说，“ 额... 欧拉老师，我们给你一个奇点，咱就叫他欧拉奇点，我们设 是正整数， 是整数，如果说这个 模 的阶等于 ，则称 为模 的一个欧拉奇点。（其中 表示 的欧拉函数）。我们今天来呢，就是让给您 个质数 ，想请您找出 最小的欧拉奇点 ”。

欧拉老师不讲武德，准备让你来解决这个问题。

不过我讲武德，所以我会告诉你一些信息，以帮助你完成这个问题：

• 设 是整数，且 和 互质，那么：使 成立的最小正整数 叫做 模 的阶，的意思就是。

当然，这里的数都太大了，你如果想要求，你可以直接使用下面的代码：

int qpow(int a, int b, int c)
{
    int res = 1;
    while(b){
        if(b & 1) res = ((long long)res * a) % c;
        a = ((long long)a * a) % c; 
        b >>= 1;
    }
    return res % c;
}

• 欧拉定理：若正整数 互质，则 其中 是欧拉函数。

• 欧拉函数：，表示的是1 ~ n 之间与n互质的数的个数。思考一下，我们给定的m是一个质数，质数的欧拉函数是多少呢？ m - 1 ！

• 我们根据上面的几个提示，可以很容易地发现， 模 的阶一定能整除 ，即 模  的阶一定是的因数，或者就是他本身，也就是说我们只需要考虑依次枚举小于他的数，根据题意判断是不是即可~。