阶

题目描述

给定素数$p$，回答$T$个询问。给定一个$a$，问最小的正数$x$满足$a^x \equiv 1 \pmod {p}$。

输入格式

第一行两个整数$p, T$。

解下来$T$行，每行一个整数$a$。

输出格式

一共$T$行，每行一个整数表示答案。

样例输入

7 3
2
3
4

样例输出

3
6
3

数据范围

对于所有数据，保证$T\leq 10^5, 1\leq a < p \leq 10^9$，并且保证$p$是素数。