0 1 1 0 2 2 2 2 0 2 1 1 2 0 0
1000
620 999571
626 999523
738 999939
1157 999335
494 999039
933 999280
997 999727
78 999899
71 999243
102 999229
1042 999118
1020 999961
1232 999598
63 999781
75 999493
935 999923
272 999387
178 999619
1179 999259
695 999322
975 999012
676 999325
1016 999526
367 999004
341 999828
949 999789
1146 999899
33 999556
899 999630
359 999954
435 999996
463 999304
891 999221
781 999138
367 999836
1006 999034
387 999079
53 999070
988 999189
693 999802
1133 999281
347 999937
1125 999431
16 999005
379 999379
228 999479
988 999488
1163 999382
495 999478
1077 999284
761 999425
1072 999248
740 999994
1115 999873
231 999906
1146 999602
1105 999413
156 999144
167 999904
567 999571
962 999240
1106 999449
773 999334
408 999486
216 999692
146 999599
885 999820
268 999568
895 999875
389 999853
846 999917
1236 999689
21 999871
1172 999366
1096 999813
1136 999667
420 999079
249 999874
555 999039
348 999124
819 999510
315 999911
774 999043
1070 999065
640 999809
753 999487
489 999906
874 999031
410 999612
558 999891
289 999838
1186 999054
691 999033
1216 999382
1153 999533
138 999998
131 999672
847 999784
842 999261
863 999482
674 999884
808 999847
96 999218
626 999204
278 999426
328 999699
848 999532
944 999453
1054 999968
759 999714
78 999746
234 999579
164 999819
1048 999977
269 999463
1091 999463
453 999381
1147 999755
1018 999146
885 999241
120 999335
270 999642
1116 999112
1059 999067
943 999520
616 999443
173 999094
358 999160
679 999432
582 999826
410 999114
672 999597
246 999424
188 999952
1054 999994
514 999147
773 999731
554 999177
290 999033
174 999606
769 999932
1230 999152
812 999793
189 999770
452 999734
122 999071
643 999682
770 999266
505 999565
555 999450
241 999950
740 999681
46 999754
632 999059
635 999246
702 999342
1146 999890
1118 999489
45 999982
1128 999766
575 999595
344 999800
537 999482
42 999422
316 999619
746 999036
508 999157
1213 999985
625 999923
951 999027
963 999797
702 999241
29 999229
983 999696
1156 999475
426 999998
285 999792
438 999114
341 999397
1045 999663
735 999255
57 999765
708 999744
605 999195
809 999230
461 999476
933 999327
551 999254
1036 999309
749 999609
326 999903
214 999152
157 999931
767 999825
1085 999762
880 999029
728 999739
1057 999531
1021 999826
816 999515
1045 999392
1224 999131
669 999437
330 999212
426 999073
126 999167
921 999343
813 999138
89 999315
165 999025
979 999488
91 999490
753 999166
940 999857
927 999295
445 999717
1195 999296
221 999486
1153 999477
670 999500
643 999737
238 999477
109 999690
573 999602
1076 999795
106 999006
46 999767
828 999468
497 999869
1233 999434
633 999278
1004 999085
982 999143
1063 999387
1119 999719
666 999445
1143 999056
584 999128
58 999922
340 999263
485 999291
80 999336
1117 999739
608 999925
676 999707
50 999182
678 999576
960 999945
622 999805
354 999185
125 999678
700 999588
1164 999941
93 999810
1212 999459
609 999116
729 999030
632 999239
660 999767
538 999347
506 999846
1088 999161
977 999780
468 999058
262 999984
728 999723
804 999258
1130 999276
977 999982
297 999037
875 999046
412 999725
798 999804
496 999859
335 999981
891 999935
1078 999445
180 999756
1009 999856
534 999777
951 999954
169 999261
727 999364
179 999357
618 999992
166 999354
550 999612
500 999736
23 999124
568 999305
933 999655
377 999963
118 999230
971 999931
207 999300
1035 999910
624 999734
772 999634
1173 999831
901 999270
10 999111
99 999744
524 999096
460 999266
1053 999373
1034 999649
653 999554
437 999694
108 999954
444 999381
864 999402
576 999482
448 999611
451 999816
635 999425
811 999598
788 999457
574 999604
1159 999609
381 999983
51 999818
693 999512
45 999095
187 999086
488 999123
872 999204
269 999001
948 999975
17 999137
1191 999929
221 999464
328 999549
922 999829
589 999242
1010 999786
369 999026
740 999442
45 999046
358 999760
479 999050
884 999553
323 999271
103 999993
167 999121
912 999654
1031 999833
1116 999124
435 999542
296 999267
106 999534
777 999473
520 999431
716 999956
660 999554
1081 999651
732 999739
1219 999751
471 999696
545 999285
1124 999655
862 999897
752 999445
507 999210
67 999737
1158 999704
209 999031
274 999134
639 999954
1154 999321
859 999491
310 999449
277 999528
140 999327
581 999930
1185 999766
24 999418
442 999543
735 999131
934 999924
99 999077
217 999822
694 999034
488 999509
224 999942
288 999472
594 999604
18 999687
524 999227
619 999867
329 999528
324 999436
371 999934
105 999625
966 999068
1217 999753
725 999652
125 999921
1051 999506
82 999704
631 999844
901 999951
97 999419
261 999203
135 999648
592 999425
586 999735
417 999576
1158 999738
547 999976
555 999389
248 999858
128 999358
966 999635
413 999033
1027 999758
950 999360
823 999378
142 999280
360 999671
745 999479
783 999150
592 999587
336 999769
444 999013
140 999753
75 999030
659 999644
162 999341
802 999089
1081 999763
268 999855
562 999185
165 999146
1077 999658
58 999104
677 999046
425 999662
582 999604
36 999266
919 999721
67 999876
108 999068
215 999882
774 999374
1094 999094
1056 999003
920 999205
489 999993
1138 999931
122 999222
1054 999376
983 999337
857 999830
1116 999886
1198 999530
872 999717
596 999715
892 999146
325 999069
106 999358
772 999296
934 999049
771 999396
1032 999306
645 999254
798 999414
514 999164
670 999030
78 999635
1055 999880
732 999446
232 999418
1031 999181
1008 999274
412 999752
453 999885
30 999572
535 999986
1127 999121
1002 999652
974 999524
88 999210
623 999039
596 999537
519 999716
456 999986
322 999614
743 999610
428 999899
989 999958
799 999788
323 999193
602 999981
1116 999695
755 999638
271 999129
549 999855
23 999770
50 999751
779 999191
926 999683
212 999188
515 999086
1051 999924
1048 999544
1134 999038
580 999522
1050 999827
538 999390
222 999062
9 999085
1011 999667
402 999647
62 999600
677 999030
794 999260
619 999314
591 999717
1156 999548
990 999590
122 999092
1082 999172
43 999304
1086 999238
140 999553
197 999315
831 999466
317 999244
927 999823
440 999336
743 999854
912 999608
817 999523
366 999173
940 999499
1196 999059
627 999189
306 999826
427 999682
216 999102
1022 999910
73 999705
1098 999348
1131 999194
774 999092
339 999244
842 999755
74 999600
731 999538
136 999770
371 999769
666 999169
832 999198
352 999201
1122 999537
933 999550
262 999539
252 999149
1048 999560
757 999658
573 999439
285 999370
218 999260
135 999553
633 999781
96 999118
12 999055
1190 999736
1052 999580
987 999798
117 999631
465 999514
410 999186
510 999155
540 999381
501 999568
643 999522
409 999637
1076 999019
760 999005
714 999651
531 999053
761 999185
792 999405
795 999830
1050 999725
1164 999889
352 999282
722 999044
689 999649
544 999952
723 999484
869 999772
129 999700
352 999807
675 999256
201 999827
121 999825
586 999552
269 999501
9 999513
583 999740
14 999358
1109 999750
25 999403
1030 999492
909 999036
894 999191
175 999336
888 999406
1195 999506
1095 999202
874 999466
337 999940
1121 999483
295 999316
822 999212
686 999327
1054 999463
1189 999780
573 999816
376 999209
781 999348
20 999734
331 999400
272 999082
712 999117
784 999134
1210 999617
981 999434
1164 999161
202 999004
157 999080
116 999151
261 999351
774 999293
627 999524
1224 999688
1095 999868
43 999222
625 999778
113 999139
157 999448
186 999569
703 999811
878 999897
1156 999276
28 999587
1016 999382
642 999281
483 999645
1220 999465
517 999986
574 999899
1182 999892
751 999131
413 999003
434 999094
433 999328
642 999828
739 999457
143 999169
821 999767
48 999682
338 999989
34 999580
185 999515
182 999132
376 999875
1047 999177
83 999720
660 999357
608 999250
903 999392
1218 999024
1055 999339
488 999347
1040 999060
83 999980
213 999792
1139 999484
982 999179
90 999293
1026 999242
145 999296
1110 999431
781 999928
867 999495
411 999194
837 999783
526 999651
254 999957
461 999464
961 999542
208 999473
533 999123
868 999226
919 999592
395 999265
109 999802
964 999483
303 999542
825 999633
1135 999399
554 999061
1204 999877
814 999465
324 999205
986 999014
510 999849
985 999938
600 999237
79 999607
489 999690
676 999578
193 999663
345 999641
505 999346
1063 999334
553 999074
598 999124
33 999570
613 999023
975 999330
191 999710
378 999421
303 999990
1232 999548
749 999034
453 999271
865 999200
869 999575
725 999033
183 999867
57 999581
1054 999451
804 999623
179 999488
1121 999400
1032 999584
652 999547
895 999158
965 999502
666 999663
685 999861
221 999853
29 999077
244 999253
814 999562
164 999126
878 999115
264 999666
403 999696
825 999620
581 999951
891 999668
453 999584
598 999606
959 999679
198 999533
1145 999047
617 999400
925 999570
205 999401
90 999517
153 999252
624 999092
294 999488
8 999310
124 999710
1169 999920
905 999127
90 999238
110 999840
315 999945
363 999823
30 999591
458 999001
187 999070
587 999841
337 999544
141 999781
863 999316
1020 999251
1045 999426
726 999044
947 999377
1046 999242
901 999420
987 999504
243 999844
675 999213
1077 999611
790 999070
108 999547
384 999138
1140 999373
417 999379
548 999523
1155 999125
268 999606
965 999635
730 999989
111 999731
1100 999888
401 999646
756 999926
966 999164
583 999415
93 999036
815 999334
526 999746
131 999111
248 999059
17 999896
647 999695
1037 999333
450 999372
131 999123
23 999629
462 999163
925 999754
685 999429
684 999888
319 999413
54 999106
767 999635
160 999556
277 999025
227 999885
1094 999062
651 999225
39 999719
273 999463
337 999987
656 999911
1145 999337
483 999840
68 999802
420 999730
579 999848
568 999244
822 999263
351 999358
125 999387
805 999219
629 999829
1013 999920
428 999122
512 999411
609 999632
314 999090
988 999093
149 999414
1225 999502
801 999792
52 999557
124 999995
7 999769
218 999676
224 999959
1179 999958
433 999119
597 999727
694 999737
1113 999066
172 999496
891 999851
226 999004
1011 999521
335 999611
1232 999091
1184 999936
988 999716
1130 999544
1159 999002
830 999509
277 999728
363 999218
90 999867
1141 999025
150 999401
605 999177
20 999223
968 999638
505 999330
999 999533
264 999852
681 999025
270 999752
708 999896
658 999824
765 999547
215 999380
920 999251
27 999362
517 999321
1234 999331
1201 999425
759 999010
428 999762
624 999885
355 999597
906 999478
390 999157
832 999670
596 999494
473 999594
164 999721
290 999600
632 999215
895 999097
637 999427
525 999824
996 999139
188 999333
1143 999284
1169 999270
892 999196
773 999469
686 999801
216 999031
48 999855
391 999822
665 999515
697 999227
1104 999247
1137 999713
904 999305
306 999831
284 999545
108 999599
1094 999478
171 999931
431 999270
900 999100
31 999232
1096 999804
771 999505
742 999378
1008 999359
936 999286
987 999749
46 999701
1208 999666
568 999147
774 999980
1186 999061
155 999817
1003 999316
614 999670
286 999147
648 999588
155 999234
959 999524
865 999142
701 999831
903 999857
818 999837
293 999591
769 999568
942 999675
246 999688
102 999601
418 999561
813 999542
469 999832
160 999286
986 999442
301 999928
107 999065
349 999700
991 999804
672 999083
305 999882
1048 999168
27 999325
674 999619
119 999234
12 999681
880 999212
575 999671
757 999318
89 999288
264 999942
401 999153
1157 999059
370 999500
1217 999833
930 999801
113 999098
69 999248
110 999449
775 999190
249 999369
607 999847
922 999725
633 999938
642 999566
529 999842
1928
1928
1915
1885
1943
1896
1891
1993
1995
1989
1890
1890
1882
1996
1993
1896
1967
1980
1885
1922
1893
1924
1890
1958
1958
1895
1887
2003
1899
1958
1948
1946
1902
1914
1958
1890
1954
1999
1891
1922
1887
1958
1888
2008
1955
1973
1891
1885
1943
1890
1914
1890
1914
1890
1973
1887
1890
1982
1982
1936
1895
1890
1914
1953
1974
1982
1902
1968
1901
1954
1905
1882
2006
1885
1890
1887
1950
1970
1937
1958
1908
1962
1914
1890
1926
1914
1943
1902
1953
1937
1967
1883
1922
1882
1886
1983
1985
1905
1905
1903
1924
1910
1990
1928
1967
1960
1905
1895
1890
1914
1993
1972
1982
1890
1968
1890
1946
1887
1890
1902
1986
1968
1890
1890
1895
1930
1981
1958
1923
1935
1953
1925
1970
1979
1890
1942
1914
1937
1967
1981
1914
1882
1909
1979
1946
1986
1926
1914
1943
1937
1970
1914
2000
1927
1927
1921
1887
1890
2000
1888
1935
1958
1939
2001
1962
1914
1943
1882
1928
1895
1895
1921
2005
1891
1886
1950
1967
1947
1958
1890
1916
1998
1921
1932
1910
1946
1896
1938
1890
1914
1960
1974
1982
1914
1890
1902
1918
1890
1890
1909
1890
1882
1926
1960
1950
1986
1897
1909
1991
1982
1892
1990
1914
1895
1897
1946
1882
1973
1886
1926
1926
1971
1989
1935
1890
1989
2000
1908
1943
1882
1927
1890
1891
1890
1890
1926
1887
1935
1998
1958
1943
1992
1890
1932
1924
1999
1923
1895
1928
1958
1986
1921
1885
1990
1882
1932
1918
1927
1926
1939
1943
1890
1892
1946
1968
1918
1910
1887
1892
1965
1902
1953
1911
1943
1959
1902
1890
1979
1890
1940
1895
1982
1918
1979
1929
1982
1938
1943
2006
1936
1896
1955
1987
1894
1975
1890
1928
1914
1885
1899
2010
1989
1941
1946
1890
1890
1926
1947
1989
1946
1903
1935
1946
1946
1927
1910
1914
1935
1885
1954
1999
1922
2000
1979
1943
1902
1968
1895
2008
1882
1973
1960
1897
1935
1890
1958
1914
2000
1958
1943
1902
1960
1989
1982
1899
1890
1890
1948
1965
1989
1914
1941
1919
1926
1890
1917
1882
1946
1938
1889
1903
1914
1943
1996
1885
1975
1967
1926
1886
1904
1964
1967
1982
1935
1883
2005
1946
1916
1896
1989
1974
1922
1943
1973
1967
1934
2007
1941
1929
1960
1960
1957
1989
1895
1882
1918
1986
1890
1992
1928
1899
1990
1968
1984
1935
1935
1951
1885
1938
1937
1970
1986
1895
1952
1890
1895
1908
1982
1958
1914
1914
1935
1959
1946
1982
1993
1926
1982
1910
1890
1968
1936
1982
1890
1998
1923
1950
1935
2003
1898
1996
1989
1974
1914
1890
1890
1897
1943
1887
1986
1890
1891
1904
1890
1882
1902
1933
1902
1960
1989
1914
1896
1914
1890
1926
1911
1942
1926
1993
1890
1917
1973
1890
1890
1953
1946
2004
1940
1888
1890
1893
1991
1928
1933
1941
1946
1960
1914
1950
1891
1911
1960
1932
1890
1914
1968
1938
2006
1999
1914
1897
1974
1942
1890
1890
1887
1935
1890
1939
1973
2010
1890
1953
1996
1923
1912
1929
1935
1886
1891
1986
1890
2001
1890
1982
1976
1908
1961
1897
1946
1914
1899
1909
1958
1895
1882
1928
1964
1950
1974
1890
1994
1890
1887
1914
1958
1905
1993
1917
1984
1957
1926
1908
1958
1889
1896
1968
1970
1890
1914
1935
1967
1973
1984
1927
1990
2009
1882
1890
1891
1987
1946
1953
1943
1938
1943
1926
1953
1890
1914
1920
1941
1914
1913
1912
1890
1885
1958
1918
1922
1938
1918
1903
1986
1958
1924
1975
1986
1935
1968
2010
1935
2008
1890
2005
1890
1899
1901
1981
1902
1882
1890
1902
1959
1889
1966
1908
1922
1890
1882
1935
1956
1914
2006
1960
1967
1921
1914
1882
1891
1885
1975
1982
1987
1968
1914
1928
1882
1890
2001
1928
1988
1982
1979
1921
1902
1886
2005
1890
1926
1943
1882
1942
1935
1884
1914
1952
1948
1949
1926
1915
1982
1908
1999
1958
2003
1979
1979
1956
1890
1992
1926
1932
1899
1882
1890
1943
1890
1992
1974
1887
1891
1990
1890
1982
1890
1914
1903
1953
1906
1941
1969
1946
1895
1975
1940
1903
1898
1954
1989
1895
1964
1908
1887
1937
1882
1909
1960
1891
1943
1891
1932
1993
1943
1924
1978
1958
1943
1890
1938
1933
2003
1931
1893
1978
1955
1964
1882
1914
1946
1903
1903
1918
1979
1998
1890
1910
1979
1889
1890
1926
1901
1895
1926
1922
1973
2005
1970
1909
1982
1902
1968
1953
1908
1935
1902
1946
1933
1895
1976
1887
1929
1897
1975
1990
1982
1928
1966
2010
1986
1885
1899
1990
1989
1962
1958
2004
1946
1979
1935
1959
1982
1903
1890
1890
1918
1895
1890
1899
1891
1970
1924
1890
1914
1989
1954
1887
1951
1938
1886
1968
1895
1918
1989
1890
1953
1914
1895
1935
1990
1909
1941
1985
1970
2008
1926
1890
1946
1985
2006
1946
1897
1922
1922
1961
1998
1914
1982
1967
1973
1890
1926
2002
1967
1959
1926
1887
1943
1995
1950
1935
1936
1908
1958
1986
1910
1928
1890
1950
1942
1932
1962
1891
1982
1882
1910
1999
1986
2010
1973
1973
1885
1949
1933
1922
1890
1982
1902
1973
1890
1959
1882
1884
1891
1887
1885
1908
1967
1958
1990
1887
1982
1932
2006
1895
1943
1890
1968
1922
1968
1921
1926
1914
1974
1897
2005
1942
1882
1882
1914
1950
1928
1958
1899
1954
1908
1933
1945
1982
1967
1927
1901
1927
1941
1891
1979
1887
1885
1902
1914
1922
1974
1999
1954
1926
1922
1890
1887
1899
1964
1967
1989
1890
1982
1949
1899
2004
1890
1914
1914
1890
1896
1891
2000
1882
1936
1914
1883
1982
1890
1930
1967
1926
1982
1895
1903
1921
1899
1908
1966
1914
1895
1970
1989
1951
1909
1946
1982
1891
1964
1989
1958
1891
1925
1964
1890
2005
1924
1986
2009
1902
1935
1914
1991
1968
1953
1885
1958
1882
1897
1988
1995
1989
1914
1970
1932
1897
1927
1926
1941
take=lambda: raw_input().strip()
calculate=lambda: list(map(int,raw_input().strip().split()))
numbers=[1,2,3,4,5,6,7,8,9,0]
num=[[1,2,3,4,5,6,7,8,9],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
ans=[[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]
def Cal(x):
	global rem,ans
	for i in xrange(len(ans[x-2])):
		for j in numbers:
			if (ans[x-2][i]*10+j)%(x)==rem[x-1]:
				ans[x-1].append(ans[x-2][i]*10+j)
	for j in xrange(len(num[x-2])):
		for i in numbers:
			if (num[x-2][j]*10+i)%(x)==rem[x-1]:
				if (num[x-2][j]%10)*10+i in primes:
					ans[x-1].append(num[x-2][j]*10+i)
				else:
					num[x-1].append(num[x-2][j]*10+i)

def count(x,A=-1,B=10**10):
	global ans
	i,count=0,0
	for i in ans[x-1]:
		if A<=i<=B:
			count+=1
	return count
	
rem=calculate()
N=int(take())
if rem[0]==1:
	for i in xrange(N):
		x=take()
		print 0
else:
	for i in xrange(2,16):
		Cal(i)
	for i in xrange(N):
		sums=0
		A,B=take().split()
		A,B=int(A),int(B)
		f,t=len(list(str(A))),len(list(str(B)))
		if f==t:
			sums=count(f,A=A,B=B)
		else:
			sums=count(f,A=A)
			for i in xrange(f+1,t):
				sums+=len(ans[i-1])
			sums+=count(t,A=-1,B=B)
		print sums