请帮助 Strange 先生解决以下问题：“求区间 $[1, N]$（$1 \le N \le 42^{42}$）中所有整数的正因数个数的最大值”。由于是 Strange 先生要解决这个问题，情况变得有些复杂，因为他讨厌数字 $P$。因此，你不需要求出 $[1, N]$ 中所有可能数字的实际最大因数个数，而只需在 $[1, N]$ 中不能被 $P$ 整除的数字中，求出正因数个数的最大值。

输入格式

输入包含多组测试数据。你的程序首先读取测试数据组数 $T$（$2 \le T \le 100$），随后是具体的测试数据。每组测试数据恰好包含三行。

第一行包含一个整数 $P$（Strange 先生讨厌的数字；$2 \le P \le 1,000,000,007$）。

第二行包含一个整数 $K$（$1 \le K \le 100$），表示需要求解的区间 $[1, N]$ 的数量。

第三行包含 $K$ 个空格分隔的整数 $N_i$（$1 \le N_i \le 42^{42}$），表示每个区间的上限。

输出格式

对于每组测试数据，输出结果应占一行。对于每个区间 $[1, N_i]$ 的计算结果，应使用空格分隔。

样例

输入样例 1

2
13
2
8 42
6
2
8 42

输出样例 1

4 9
4 8

说明

在每组测试数据中，你需要求出区间 $[1, 8]$ 和 $[1, 42]$ 内数字的最大因数个数。

如果 Strange 先生讨厌 $P=13$，则在第一个区间中，最大因数个数为 $4$，在数字 $6$（因数为 1, 2, 3, 6）和 $8$（因数为 1, 2, 4, 8）处达到；在第二个区间中，最大因数个数为 $9$，在数字 $36$ 处达到。

如果 Strange 先生讨厌 $P=6$，则数字 6, 12, 18, 24, 30, 36, 42 都是被禁止的。因此，在第一个区间中，同样的最大因数个数 $4$ 只能在数字 $8$ 处达到；在区间 $[1, 42]$ 中，没有数字拥有 $9$ 个因数，但最大因数个数 $8$ 可以在数字 $40$ 处达到。