题目描述

小 Q 学习了一种判断大数是否是 $p$ 的倍数的方法。该方法在 $b$ 进制下进行，需要将数字按每 $k$ 位分段，然后进行一系列运算。

对于给定的 $b, p$，小 Q 想知道最小的正整数 $k$，使得无论输入如何，输入和对应的输出要么同时是 $p$ 的倍数，要么同时不是 $p$ 的倍数，或者报告这样的 $k$ 不存在。

注意 $p$ 不一定是质数。

输入格式

第一行包含两个正整数 $T, p$，表示测试数据组数与方法的 $p$ 参数。

接下来 $T$ 行每行一个整数 $b$ 表示每组测试数据的进制。

保证：

• $1 \le T \le 10^5$
• $2 \leq p \leq 10^{15}$
• $2 \leq p < b \leq 10 \times p$

输入中的所有数字按照十进制给出。

输出格式

对于每组数据输出一行，若不存在合法的 $k$ 输出 -1，否则输出最小的满足条件的正整数 $k$。

样例

输入

2 9
14
16

输出

2
-1

数据范围与提示

为了选手们的身心健康，下发文件中的 down.cpp 中实现了大整数取模乘法函数 mul(A, B, P)，你需要保证 $A,B \in [0,P-1]$，函数会返回 $(A \times B) \bmod P$。你可以自由选择使用或者不使用这份代码。其中需要保证你调用时 $A,B,P$ 均不超过 $10^{15}$。