問題文

高橋君は、数列を作って、それに関していろいろ操作を施すのが好きです。特に、区間の和や区間の最大公約数を計算したりといった区間に関していろいろ操作を施すのが大好きです。

そこで、高橋君は、ある数列に関して、区間の最大公約数がとある値 x となるような区間の数を数えることにしました。 高橋君は、プログラムを使ってこの問題を解いたのですが、長い数列になればなるほど、時間がとても掛かってしまうことに気づきました。

あなたの仕事は、高橋君のために、数列が長いときでも高速に動作するプログラムを書くことです。 また、オマケ機能として、同じ数列に対して、いくつか x の候補があっても、全ての x　について計算できるよう、問い合わせ機能をつけてあげることにしました。

あなたには、 長さ n の数列 A=\{a_1,a_2,..,a_n\} が与えられます。また、問い合わせの数 m と、 x_1,x_2,..,x_m も与えられます。 それぞれの x_i (1 ≦ i ≦ m) について、区間に含まれる全ての数の最大公約数が x_i となるような区間 [s,t] (1 ≦ s ≦ t ≦ n) の数を出力してください。

例えば、A=\{1,2,4\} のとき、最大公約数が1となる区間は、[1,1],[1,2],[1,3]の3つであり、最大公約数が2となる区間は、[2,2],[2,3] の2つであり、 最大公約数が4となる区間は、[3,3] のみです。

入力例1

3 4
1
2
4
1
2
3
4

出力例1

3
2
0
1

与えられる数列は、問題文中のものです。

入力例2

6 7
12
6
4
3
2
1
1
2
3
4
6
12
8

出力例2

13
3
1
1
2
1
0

入力例3

5 8
4
6
42
28
41
1
2
4
6
7
14
14
41

出力例3

4
4
1
2
0
1
1
1