Modular Order

Problem Description

Given a prime $p$, answer $T$ queries. Given an $a$, find the smallest positive integer $x$ such that $a^x \equiv 1 \pmod p$.

Input Format

The first line contains two integers $p, T$.

The next $T$ lines each contain one integer $a$.

Output Format

A total of $T$ lines, each containing one integer: the answer.

Sample Input

7 3
2
3
4

Sample Output

3
6
3

Constraints

For all data, $T\leq 10^5$, $1\leq a < p \leq 10^9$ are guaranteed, and $p$ is prime.