쿼리는 위수입니까?

이 문제는 함수 구현 문제입니다.

$2 \leq N \leq 10^9$를 만족하는 정수 $N$이 숨겨져 있다. 이때 ask() 함수를 $1\,000$번 이하로 사용하여 숨겨진 $N$을 맞혀라.

함수 구현

제출하는 코드는 #include "order.h"를 통해 order.h 헤더파일을 포함해야한다. 제출하는 코드는 다음을 구현해야한다.

int find()

• 이 함수는 숨겨진 정수 $N$을 반환해야 한다.

find() 함수 내부에서는 다음의 함수를 호출할 수 있다.

int ask(long long a)

• $a$는 $1 \leq a \leq 9 \cdot 10^{18}$을 만족해야하며, 만족하지 않을 경우 틀렸습니다를 받게 된다.
• 반환값은 다음과 같다.
  • $\gcd(a,N)=1$이면, 법 $N$에서 $a$의 위수를 반환한다. 즉, $a^r \equiv 1 \pmod N$을 만족하는 최소 양의 정수 $r$을 반환한다.
  • $\gcd(a,N)\neq 1$이면, $0$을 반환한다.
• 이 함수는 find()에서 최대 $1\,000$번 호출 가능하다. 이를 초과하여 호출한 경우 틀렸습니다를 받게 된다.

제출하는 코드의 어떤 부분에서도 입출력이 있어서는 안 된다.