Prof. Chen 目前在 Pigetown 大学任教。Pigetown 大学共有 $n$ 盏灯，编号为 $1, 2, \dots, n$，以及 $n$ 个开关，编号为 $1, 2, \dots, n$。Pigetown 大学的照明控制系统非常奇特：按下编号为 $d$ 的开关会打开所有编号为 $d$ 的倍数的灯。由于该系统没有关闭功能，如果按下某个开关后没有任何灯从关闭状态变为开启状态，控制系统就会发出警告。

初始时，所有灯都是关闭的。Prof. Chen 总共按下了 $m$ 次开关，第 $i$ 次操作按下的是编号为 $a_i$ 的开关。你的任务是模拟这个照明控制系统，在每次操作后输出新开启的灯的数量，如果没有任何新的灯被开启，则发出警报。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 2 \cdot 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n, m \le 2 \cdot 10^5$)，分别表示灯的数量和 Prof. Chen 按下开关的次数。

接下来一行包含 $m$ 个整数，第 $i$ 个整数 $a_i$ ($1 \le a_i \le n$) 表示 Prof. Chen 在第 $i$ 次操作中按下的开关。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，打印 $m$ 行。对于第 $i$ 行，如果第 $i$ 次操作中有新的灯被开启，输出新开启的灯的数量。否则，输出 “the lights are already on!”。

样例

输入 1

2
5 3
2 4 1
100 2
100 100

输出 1

2
the lights are already on!
3
1
the lights are already on!