Computing Order Modulo Prime

Given a prime number \( p \) and an integer \( x \) satisfying \( 1 \le x < p \), the order of \( x \) modulo \( p \) is defined as the smallest positive integer \( t \) such that \( x^t \equiv 1 \pmod{p} \). It can be proven that such a positive integer always exists.

Your task is to help compute the order of \( x \) modulo \( p \) for several queries.

inputFormat

The input consists of:

• The first line contains two integers \( p \) and \( q \), where \( p \) is a prime number and \( q \) is the number of queries.
• Each of the following \( q \) lines contains a single integer \( x \) satisfying \( 1 \le x < p \).

outputFormat

For each query, output a single line containing the order of \( x \) modulo \( p \).

sample

7 3
2
3
4

3
6
3