题目描述
You are given an array A containing N integers. Let P be the product of all the elements of A. Your task is to answer Q queries. Each query consists of a single integer X. In order to answer a query, you have to find the number of trailing 0's in P represented in base X.
For more information about base representation of a number, please refer here.
Constraints
1 ≤ N, Ai, Q ≤ 10^5
2 ≤ X ≤ 10^5
Input format
The first line contains a single integer N. The second line contains N space separated integers, representing the array A. The third line contains a single integer Q. Next Q lines follow, each containing a single integer X, denoting a single query.
Output format
Output exactly Q lines. In the i^th of them, output the answer to the i^th query.
SAMPLE INPUT
4
3 4 1 1
1
2
SAMPLE OUTPUT
2
Explanation
The value of P is 4 * 3 * 1 * 1 = 12. 12 in base 2 representation is "1100" which has 2 trailing zeroes.
输入格式
见题面
输出格式
见题面
样例输入
96
2 65 31 35 1 22 61 50 46 35 41 63 93 1 59 71 13 61 1 62 57 51 99 27 89 35 57 61 16 12 74 6 21 81 15 40 51 23 9 93 12 8 65 46 66 9 31 27 15 81 73 65 71 48 81 11 25 99 1 22 19 91 59 33 51 1 71 75 51 21 56 77 93 45 98 49 33 5 77 96 31 20 69 92 8 41 36 33 21 53 81 26 41 25 69 30
49
79
53
29
69
56
57
59
31
90
93
7
65
81
29
54
56
23
2
40
74
16
44
77
44
56
27
84
74
53
74
20
20
8
41
67
71
39
60
35
60
76
24
40
23
77
96
81
85
4
样例输出
44
9
21
15
44
70
59
2
83
67
191
191
84
8
20
122
83
0
16
253
109
381
0
3
381
1
3
2
4
16
1
42
36
2
381
446
5
253
11
65
279
63
155
109
65
1
1
9
1
282
63
0
19
670
100
54
18
59
65
26
27
36
123
70
14
381
9
49
90
279
15
11
2
2
0
83
83
670
4
42
11
116
8
446
4
139
5
17
155
16
35
9
423
65
65
1
3
123
1
28
13
21
5
116
42
244
190
63
381
191
1
2
8
67
0
123
84
558
244
19
279
244
10
34
67
5
59
18
2
5
244
8
23
6
65
84
434
670
0
5
90
5
0
9
253
1
34
30
141
37
122
2
42
100
65
5
2
49
21
49
2
5
677
10
244
122
253
90
5
1340
30
3
446
1
670
17
2
2
434
30
434
49
5
59
2
566
8
42
558
191
381
155
49
8
0
7
84
381
7
0
27
2
37
307
100
67
282
126
5
65
0
49
122
34
18
139
123
282
4
30
15
83
434
1
376
1
5
566
7
36
11
67
677
123
381
22
3
1132
7
191
1
1
381
253
4
2
2
217
42
109
155
84
0
54
1
65
5
282
67
58
0
338
89
2
3
1
282
434
1
1
1
27
122
84
244
42
282
11
17
58
31
1
558
17
63
3
30
100
20
13
116
42
381
16
89
24
84
27
31
434
84
282
0
22
89
8
6
282
253
84
19
84
5
22
5
49
58
6
2
89
139
0
90
3
30
2
279
191
279
44
122
36
1
38
1128
566
30
36
670
24
27
49
446
1
90
1
42
22
253
42
27
123
27
434
9
2
83
5
90
1
14
1132
116
5
116
59
381
67
434
139
3
84
6
381
27
10
37
381
10
566
15
42
90
19
83
139
63
0
109
191
0
54
4
6
10
19
244
49
69
14
3
67
84
5
90
17
25
5
123
1128
381
116
139
9
30
558
15
3
123
6
244
18
17
217
30
558
27
244
25
54
9
2
191
23
23
70
155
59
36
122
244
7
7
4
42
7
7
20
1
83
30
59
13
279
21
23
7
3
109
89
37
5
244
58
670
253
7
9
16
4
191
122
139
10
483
139
2
49
49
846
381
24
446
84
15
381
434
10
338
253
0
4
10
1
434
446
65
90
2
27
2
3
244
65
217
83
5
49
191
3
100
24
33
423
139
5
155
10
139
0
4
1
30
116
8
244
19
122
5
116
2
4
244
483
42
2
42
7
65
0
65
65
100
44
109
155
564
4
244
282
155
279
381
116
2
42
434
11
21
191
0
21
65
83
244
122
28
4
16
5
2
139
253
65
12
24
244
19
8
670
36
20
122
89
139
13
4
19
67
5
123
5
1
84
67
44
65
7
2
2
244
1
59
37
2
253
279
558
6
84
0
244
89
70
4
1
65
381
16
33
244
37
677
1
282
2
0
30
24
155
2
83
15
566
5
2
253
122
63
282
2
15
3
17
26
63
44
244
282
15
109
5
27
0
338
123
10
4
282
35
139
4
24
67
6
18
2
90
244
6
123
155
122
1
2
38
54
9
84
18
42
89
558
2
109
0
2
3
67
27
89
0
1
9
13
126
4
126
59
14
123
191
65
65
2
283
11
9
44
10
0
6
1
2
253
7
3
116
483
58
1
282
6
42
12
434
25
253
90
139
70
3
58
10
191
42
253
3
3
8
22
5
27
2
63
2
6
84
282
63
9
139
89
4
6
65
54
21
65
244
16
16
90
381
244
282
139
17
11
83
0
377
5
4
2
381
381
434
6
1
2
27
338
0
155
18
49
89
89
558
63
122
58
30
0
42
42
253
65
3
6
58
16
253
2
37
191
16
0
1
11
381
3
5
1
89
44
16
7
21
5
6
65
6
6
2
109
2
677
67
17
7
42
155
20
59
122
7
65
8
5
2
3
116
558
7
12
2
3
27
6
3
14
20
1
122
3
89
65
16
282
139
42
90
253
3
11
139
65
18
677
83
10
109
2
11
1
21
1
5
0
7
434
4
15
5
65
139
5
65
70
8
65
376
253
566
434
4
7
434
3
6
3
19
2
20
13
0
109
1
89
2
191
49
253
4
558
36
17
1
109
4
0
122
90
11
569
0
54
217
1132
7
381
7
5
83
282
13
670
49
3
3
116
253
27
2
10
381
446
15
14
244
217
253
83
22
2
90
4
10
89
191
36
1
49
2
42
122
122
8
282
42
22
20
1
90
15
381
0
0
30
89
116
4
32
244
30
59
5
14
558
3
27
3
0
122
4
20
7
190
122
109
282
7
1
0
69
36
244
123
116
10
0
282
26
9
1132
70
2
191
24
4
191
84
2
8
191
36
253
63
36
49
853
10
116
54
191
1
15
190
139
1
100
8
566
58
244
19
2
12
2
9
282
26
8
139
49
24
3
6
20
84
4
3
5
1
122
18
2
26
126
1
49
49
155
225
19
5
10
2
4
122
100
5
282
4
21
6
89
4
123
42
670
26
13
122
50
35
123
2
13
67
5
83
0
558
100
54
1
27
90
90
2
65
139
5
33
4
381
12
7
89
7
13
89
1
2
260
6
1
11
0
2
27
36
3
16
65
7
126
3
12
65
0
3
5
1
49
54
30
1
10
109
564
11
65
25
1
7
1132
3
2
15
376
139
65
65
1
8
31
20
3
4
89
126
0
54
9
2
84
42
83
70
0
122
6
0
3
5
9
90
446
27
123
5
0
12
3
1
17
17