#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
set<int> multiset;
int n, temp, q, a, b, how_many, x;
bool divided;
cin >> n;
while(n--) {
cin >> temp;
multiset.insert(temp);
}
cin >> q;
while(q--) {
cin >> a >> b;
how_many = 0;
for (int i = a; i <= b; i++) {
divided = false;
for (int x : multiset) {
if (i % x == 0) {
divided = true;
break;
}
}
if(!divided) how_many++;
}
cout << how_many << '\n';
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CgkKCXNldDxpbnQ+IG11bHRpc2V0OwoJaW50IG4sIHRlbXAsIHEsIGEsIGIsIGhvd19tYW55LCB4OwoJYm9vbCBkaXZpZGVkOwoJY2luID4+IG47Cgl3aGlsZShuLS0pIHsKCQljaW4gPj4gdGVtcDsKCQltdWx0aXNldC5pbnNlcnQodGVtcCk7Cgl9CgkKCWNpbiA+PiBxOwoJd2hpbGUocS0tKSB7CgkJY2luID4+IGEgPj4gYjsKCQlob3dfbWFueSA9IDA7CgkJZm9yIChpbnQgaSA9IGE7IGkgPD0gYjsgaSsrKSB7CgkJCWRpdmlkZWQgPSBmYWxzZTsKCQkJZm9yIChpbnQgeCA6IG11bHRpc2V0KSB7CgkJCQlpZiAoaSAlIHggPT0gMCkgewoJCQkJCWRpdmlkZWQgPSB0cnVlOwoJCQkJCWJyZWFrOwoJCQkJfQoJCQl9CgkJCWlmKCFkaXZpZGVkKSBob3dfbWFueSsrOwoJCX0KCQljb3V0IDw8IGhvd19tYW55IDw8ICdcbic7Cgl9CglyZXR1cm4gMDsKfQ==
MTAwCjI2MTggNTgzMSAyNzQ3IDczMzQgNzA2MyA1Mjk1IDYyMTYgMjAwNyAxOTE1IDI3MDYgMzEzMyAxNzg0IDUwOTUgODY3MyAzMjU5IDIxNyA5MTggNzEyMyAxMTMgNjAyNCA2MDEyIDk4MDMgODgwOSAzNDQ2IDY2NyA5MzQ0IDY3IDIzNTAgOTU1MyAyODMwIDk4OTIgNzIwNiA4MzkxIDY2NDIgODAyNCA3NDUzIDQ0NTAgNTg5NSAxNDggNDkzMiAxMCAzNzUzIDkzMiA5MTkyIDY2OTEgMzA2NiA3MjggMzkwMiA0NzY2IDgyNjQgMzg4NyA3Njg5IDEyNjUgMzAxMSAzMDggMjYyMyA1NDc4IDUyODAgNzM2MyA2NjgzIDMzMDcgMzc0MCA5ODg0IDgwOTQgMjY2NCAyNjI0IDc5MjEgNTExIDgwMjAgODc5NiAzMjY3IDEwNTggNTc3MCAxNTUyIDc4NTggMTIzMyA3NDY5IDgzNTAgNzAyMyAxNDk3IDYzOTMgNDg1MiAzNzU2IDgzMTkgNzcgMzIzMiA5MjEwIDI1NjQgODk0NCA1MjcyIDE4MDggNzUyMyAyNDg2IDI1MDggNzIxNyA3ODk2IDM1MyA1MDEzIDUxNzkgOTc3Ngo5OAoyMTc3IDk1NDIKNzk1NCA4OTg1Cjc1MyA1MzgyCjc4NiA3NzA2CjgzNCA1NjQ1CjQ5NDcgNTMzMwoyMTEgNzc5Nwo1NDg3IDY2ODUKMzkxMSA1Nzg2CjQwNDkgODMzMQo3NTExIDk3MjAKNDcwOSA2MzE2CjIyNTMgODcxMAo1NTYxIDg3NDIKMjY0OSA2MDE4CjU2OTggODEyMAoxOTcgMzcwNAo2NTEgNDA0MQo4MTQgODE1MAo0NDUgNTE4NQozMDg3IDM3MDYKMjI5NiAyOTQ1CjY1ODggOTExMgozMzc5IDY5NDEKNDk4NCA1MDk3CjM5NTkgOTc3MQo0NDA2IDgwNzcKMTM0NSA4OTk3CjIyMTcgNTY1MgoyNTQxIDg4MjAKMjIyOCA5MjIyCjQ1NjcgODE3NgoxOTA3IDg3MzEKMzkzMiA3MjcwCjQwNTkgNDg0MAozMzg0IDc2ODYKODE3IDg1NzQKNDkyMyA1Njc0CjYyOSA4ODQyCjIwNCA0NDYyCjIyODcgODM5MgoyNjcxIDI2ODMKMzQ2NCA2NTY3CjEyMTYgNzgzNQoyMTc4IDM0MDUKMTAwNSA4MzAzCjExMTggNTAwNQozNTc1IDYwMjcKNzAwIDczOTcKNTQyMyA2MzkzCjkzMyA5NjYKMjAgOTYKNDQ0IDc4OQoxNDAgMjcwCjYxOSA4MzQKMjQ4IDk0NAo2OTMgOTY5CjI2NSAzOTkKNjAzIDgzOQo4MjIgOTIyCjQwNCA2OTYKMzM4IDY4NAo0NDYgNTA4CjM0NiA5NzcKMzYgNzY3CjI3IDUxMAo2MTUgNzAyCjI4NiA0OTIKMTY0IDgyNQoyMDcgNDE2CjUyNSA4OTYKODkgNzIyCjExMSA4MjMKMzY5IDkzNAoxMzggMTk0CjUzOCA3NzcKOTYgMzc1Cjg3IDEzNwo3ODUgODg1Cjc5OSA4MjIKNDA0IDQzMQoyNDkgNTU5CjEyNSAyMjEKMTIzIDgyOAoyNzkgNDI2CjEzNiA2NDcKNDI0IDYyOQo5MCA1NjYKOTQyIDk0OAoxOTIgMjE3CjQwNyA0NDEKMzExIDY5MgoxODggMjMwCjQ0NiA0OTAKMjk4IDQwNgozMTQgNjM1CjQzMCA4MTAKMSAxMDAwMDA=
100
2618 5831 2747 7334 7063 5295 6216 2007 1915 2706 3133 1784 5095 8673 3259 217 918 7123 113 6024 6012 9803 8809 3446 667 9344 67 2350 9553 2830 9892 7206 8391 6642 8024 7453 4450 5895 148 4932 10 3753 932 9192 6691 3066 728 3902 4766 8264 3887 7689 1265 3011 308 2623 5478 5280 7363 6683 3307 3740 9884 8094 2664 2624 7921 511 8020 8796 3267 1058 5770 1552 7858 1233 7469 8350 7023 1497 6393 4852 3756 8319 77 3232 9210 2564 8944 5272 1808 7523 2486 2508 7217 7896 353 5013 5179 9776
98
2177 9542
7954 8985
753 5382
786 7706
834 5645
4947 5333
211 7797
5487 6685
3911 5786
4049 8331
7511 9720
4709 6316
2253 8710
5561 8742
2649 6018
5698 8120
197 3704
651 4041
814 8150
445 5185
3087 3706
2296 2945
6588 9112
3379 6941
4984 5097
3959 9771
4406 8077
1345 8997
2217 5652
2541 8820
2228 9222
4567 8176
1907 8731
3932 7270
4059 4840
3384 7686
817 8574
4923 5674
629 8842
204 4462
2287 8392
2671 2683
3464 6567
1216 7835
2178 3405
1005 8303
1118 5005
3575 6027
700 7397
5423 6393
933 966
20 96
444 789
140 270
619 834
248 944
693 969
265 399
603 839
822 922
404 696
338 684
446 508
346 977
36 767
27 510
615 702
286 492
164 825
207 416
525 896
89 722
111 823
369 934
138 194
538 777
96 375
87 137
785 885
799 822
404 431
249 559
125 221
123 828
279 426
136 647
424 629
90 566
942 948
192 217
407 441
311 692
188 230
446 490
298 406
314 635
430 810
1 100000