A - Uncommon

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600

問題文

N 個の異なる整数 a_1, a_2, ..., a_N と整数 M が与えられます。

1 以上 M 以下のそれぞれの整数 i について、a_1, a_2, ..., a_N のうち i と互いに素であるものの個数を求めてください。

注釈

二つの整数 ab互いに素 であるとは、ab をともに割り切る正の整数が 1 以外に存在しないことをいいます。

例えば、67 は互いに素ですが、68 はともに 2 で割り切れるため互いに素ではありません。

制約

  • 1 ≤ N, M ≤ 10^5
  • 1 ≤ a_i ≤ 10^5
  • a_i はすべて異なる。
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1
a_2
:
a_N

出力

M 行出力せよ。i 行目 (1 ≤ i ≤ M)a_1, a_2, ..., a_N のうち i と互いに素であるものの個数を出力すること。


入力例 1

4 3
6
7
8
9

出力例 1

4
2
2

6, 7, 8, 9 のうち、

  • 1 と互いに素であるものは 6, 7, 8, 94
  • 2 と互いに素であるものは 7, 92
  • 3 と互いに素であるものは 7, 82

です。


入力例 2

1 5
100000

出力例 2

1
0
1
0
0

入力例 3

5 7
14142
17320
22360
24494
26457

出力例 3

5
1
3
1
3
0
5