1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
 
#define st first
#define nd second
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
#define PI 3.14159265359
 
using namespace std;
 
typedef long long ll;
constexpr ll MOD = 1000000007;
constexpr int MXN = 200000+7 + 10, CZAPA = (1<<20), INF = 1000000000;

ll tab[] = {0, 52990,43952,42351,40453,39408,1066,38678,13620,30997,22984,0,43933,42478,40112,39540,974,38915,13557,31139,23058,0,42453,42268,38850,39370,0,38730,12780,31060,21868,0,40148,38806,40112,35995,911,38806,12148,27962,23006,0,39547,39344,35970,39403,0,35979,11869,31168,20190,0,974,0,911,0,1065,0,457,0,654,0,38912,38774,38809,35915,0,38938,11401,28037,21833,0,13639,12751,12098,11922,457,11321,13571,9129,6643,0,31139,31088,27968,31144,0,28069,9067,31101,15397,0,23035,21868,23022,20178,661,21846,6652,15373,22963,0,0,0,0,0,0,0,0,0,0,0,44117,42288,40327,39350,1041,38781,13498,31076,22987,0,42279,42404,38687,39510,0,38809,12769,31022,21900,0,40253,38678,40413,35875,876,38800,12119,28024,22921,0,39388,39500,35868,39465,0,35937,11859,31005,20202,0,1036,0,876,0,953,0,457,0,622,0,38785,38806,38800,35924,0,38751,11380,27895,21863,0,13542,12798,12061,11917,449,11337,13634,9128,6672,0,31076,31034,28043,30975,0,27922,9068,31016,15376,0,22960,21900,22949,20165,622,21872,6703,15382,23049,0,0,0,0,0,0,0,0,0,0,0,42268,42418,38682,39468,0,38828,12790,31031,21907,0,42376,42260,38895,39431,0,38800,12785,31144,21849,0,38666,38873,38770,35976,0,38781,11429,27918,21865,0,39514,39422,35974,39480,0,36013,11840,31146,20185,0,0,0,0,0,0,0,0,0,0,0,38799,38800,38841,36001,0,38837,11398,28063,21864,0,12810,12827,11360,11883,0,11384,12803,9102,6175,0,31031,31162,27909,31110,0,28050,9055,31124,15396,0,21885,21849,21869,20164,0,21837,6177,15395,21878,0,0,0,0,0,0,0,0,0,0,0,40308,38687,40401,35875,876,38739,12031,28051,22949,0,38678,38922,38773,35993,0,38841,11412,27897,21848,0,40404,38748,40224,35963,849,38892,12078,28069,22909,0,35871,35979,35981,35933,0,35872,10490,27906,20178,0,876,0,849,0,836,0,398,0,633,0,38808,38781,38921,35878,0,38664,11430,27953,21858,0,12101,11384,12044,10519,398,11366,12122,7937,6686,0,28051,27932,28037,27901,0,27925,7878,27979,15371,0,22921,21848,22928,20175,627,21832,6713,15352,23004,0,0,0,0,0,0,0,0,0,0,0,39365,39503,35903,39490,0,35924,11847,30990,20198,0,39471,39403,35976,39482,0,36014,11895,31118,20138,0,35891,35974,35972,35930,0,35866,10519,27922,20178,0,39497,39416,35918,39554,0,35975,11830,31148,20178,0,0,0,0,0,0,0,0,0,0,0,35937,35987,35880,36017,0,35965,10506,28031,20211,0,11883,11872,10490,11895,0,10465,11883,9142,5660,0,30990,31155,27895,31112,0,28032,9079,31021,15372,0,20181,20138,20191,20186,0,20205,5695,15381,20169,0,0,0,0,0,0,0,0,0,0,0,1036,0,876,0,953,0,449,0,622,0,0,0,0,0,0,0,0,0,0,0,876,0,849,0,835,0,398,0,633,0,0,0,0,0,0,0,0,0,0,0,953,0,836,0,974,0,476,0,654,0,0,0,0,0,0,0,0,0,0,0,449,0,398,0,476,0,485,0,262,0,0,0,0,0,0,0,0,0,0,0,618,0,633,0,654,0,262,0,661,0,0,0,0,0,0,0,0,0,0,0,38770,38795,38808,35913,0,38749,11337,27880,21876,0,38814,38784,38809,36013,0,38827,11405,28052,21862,0,38739,38783,38938,35905,0,38678,11430,27925,21879,0,35968,36001,35872,36012,0,36001,10468,28015,20229,0,0,0,0,0,0,0,0,0,0,0,38756,38806,38690,35995,0,38806,11408,27962,21885,0,11380,11370,11366,10509,0,11381,11381,7933,6177,0,27880,28083,27953,28006,0,27960,7894,27901,15362,0,21877,21862,21869,20190,0,21900,6179,15358,21833,0,0,0,0,0,0,0,0,0,0,0,13512,12810,12101,11859,449,11378,13602,9092,6685,0,12790,12825,11401,11872,0,11443,12826,9055,6137,0,12058,11373,12073,10505,398,11366,12124,7920,6661,0,11917,11895,10455,11889,0,10480,11852,9110,5695,0,449,0,398,0,476,0,476,0,261,0,11361,11343,11430,10540,0,11358,11440,7907,6106,0,13617,12828,12076,11858,476,11419,13593,9113,6699,0,9092,9102,7891,9074,0,7913,9066,9046,4192,0,6638,6137,6679,5660,262,6131,6688,4153,6601,0,0,0,0,0,0,0,0,0,0,0,31076,31034,28043,30975,0,27922,9068,31016,15376,0,31022,31178,27932,31119,0,28073,9083,31149,15373,0,28024,27897,28064,27934,0,27928,7909,28002,15352,0,31005,31144,27897,31101,0,28031,9074,31031,15394,0,0,0,0,0,0,0,0,0,0,0,27895,28039,27941,28032,0,27939,7933,27918,15362,0,9128,9058,7860,9110,0,7894,9063,9083,4196,0,31016,31161,27975,31022,0,27932,9062,31022,15372,0,15382,15373,15371,15359,0,15366,4200,15367,15360,0,0,0,0,0,0,0,0,0,0,0,22966,21907,22934,20156,622,21877,6638,15341,23048,0,21885,21849,21869,20164,0,21837,6177,15395,21878,0,22948,21865,22900,20191,633,21858,6685,15363,23005,0,20173,20185,20178,20170,0,20190,5601,15377,20197,0,622,0,633,0,651,0,262,0,661,0,21866,21864,21832,20229,0,21887,6139,15378,21842,0,6685,6175,6618,5645,262,6144,6640,4192,6652,0,15341,15396,15369,15355,0,15387,4153,15345,15351,0,23059,21878,22994,20190,661,21827,6661,15391,22969,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,43823,42399,40091,39471,1015,38795,13624,31021,22994,0,42406,42228,38924,39422,0,38784,12842,31158,21860,0,40110,38912,40266,35978,958,38783,12122,27932,22948,0,39514,39401,35993,39445,0,36001,11856,31138,20191,0,1017,0,958,0,1079,0,434,0,652,0,38828,38792,38812,36016,0,38806,11443,28050,21871,0,13640,12785,12098,11890,434,11370,13540,9084,6667,0,31021,31168,27918,31118,0,28083,9058,31138,15367,0,23005,21860,22950,20185,652,21862,6666,15365,22960,0,0,0,0,0,0,0,0,0,0,0,42407,42254,38915,39403,0,38793,12827,31144,21856,0,42250,42405,38730,39499,0,38812,12802,30987,21826,0,38895,38785,38806,35962,0,38891,11372,28079,21847,0,39403,39500,35979,39448,0,35878,11841,31001,20191,0,0,0,0,0,0,0,0,0,0,0,38739,38783,38938,35905,0,38678,11430,27925,21879,0,12853,12819,11321,11895,0,11426,12742,9114,6189,0,31144,31005,28069,31024,0,27957,9090,31060,15362,0,21870,21826,21846,20178,0,21852,6156,15369,21885,0,0,0,0,0,0,0,0,0,0,0,40090,38924,40281,35974,958,38809,12108,27901,22950,0,38912,38774,38809,35915,0,38938,11401,28037,21833,0,40269,38799,40340,35968,974,38715,12086,27934,22993,0,35939,35963,35937,35987,0,36017,10480,28025,20180,0,958,0,974,0,962,0,351,0,629,0,38789,38891,38751,36015,0,38873,11386,28032,21917,0,12155,11377,12036,10514,351,11372,12005,7911,6670,0,27901,28065,27922,28052,0,28042,7897,27947,15377,0,22948,21833,22995,20178,629,21904,6646,15359,22921,0,0,0,0,0,0,0,0,0,0,0,39468,39406,35979,39478,0,36016,11872,31110,20155,0,39431,39490,35962,39459,0,35869,11892,31014,20163,0,35976,35979,35913,36014,0,36011,10514,28083,20186,0,39480,39458,36013,39365,0,35837,11853,31016,20192,0,0,0,0,0,0,0,0,0,0,0,36001,35872,36012,35871,0,35868,10473,28002,20183,0,11883,11880,10480,11890,0,10498,11887,9084,5672,0,31110,31038,28050,31028,0,28014,9054,31144,15339,0,20164,20163,20157,20198,0,20184,5668,15372,20181,0,0,0,0,0,0,0,0,0,0,0,1015,0,958,0,1086,0,434,0,652,0,0,0,0,0,0,0,0,0,0,0,958,0,974,0,962,0,351,0,629,0,0,0,0,0,0,0,0,0,0,0,1079,0,962,0,1036,0,417,0,622,0,0,0,0,0,0,0,0,0,0,0,444,0,351,0,415,0,425,0,239,0,0,0,0,0,0,0,0,0,0,0,652,0,629,0,622,0,239,0,618,0,0,0,0,0,0,0,0,0,0,0,38806,38800,38789,35991,0,38827,11370,28039,21837,0,38808,38781,38921,35878,0,38664,11430,27953,21858,0,38809,38919,38739,36020,0,38912,11379,28042,21887,0,36030,35905,35975,35828,0,35875,10480,27979,20200,0,0,0,0,0,0,0,0,0,0,0,38850,38682,38858,35871,0,38792,11419,28041,21870,0,11443,11409,11349,10504,0,11379,11373,7902,6173,0,28039,27941,28032,28011,0,28047,7910,28046,15331,0,21867,21858,21892,20201,0,21860,6158,15381,21877,0,0,0,0,0,0,0,0,0,0,0,13593,12853,12136,11856,434,11398,13591,9034,6616,0,12827,12773,11377,11880,0,11386,12803,9090,6093,0,12128,11375,12067,10511,351,11349,12047,7949,6637,0,11890,11892,10466,11838,0,10513,11869,9043,5668,0,434,0,351,0,415,0,425,0,239,0,11405,11366,11379,10526,0,11347,11400,7938,6133,0,13620,12831,12030,11841,425,11412,13530,9085,6684,0,9034,9114,7905,9058,0,7916,9070,9067,4148,0,6666,6093,6638,5672,239,6126,6702,4196,6638,0,0,0,0,0,0,0,0,0,0,0,31021,31168,27918,31118,0,28083,9058,31138,15367,0,31158,30975,28065,31046,0,27940,9150,31048,15360,0,27932,28037,27901,28073,0,28028,7864,27991,15359,0,31138,31049,28063,31009,0,28002,9058,31144,15374,0,0,0,0,0,0,0,0,0,0,0,28050,27954,28009,28014,0,28020,7902,28079,15368,0,9084,9118,7880,9043,0,7910,9020,9095,4203,0,31138,31076,27960,31158,0,28065,9126,31138,15368,0,15365,15360,15377,15363,0,15360,4175,15366,15382,0,0,0,0,0,0,0,0,0,0,0,23004,21856,23003,20157,652,21847,6666,15362,22966,0,21870,21826,21846,20178,0,21852,6156,15369,21885,0,22982,21847,22986,20157,633,21917,6608,15372,22948,0,20138,20191,20186,20175,0,20201,5632,15331,20173,0,652,0,629,0,622,0,239,0,622,0,21863,21879,21904,20200,0,21857,6124,15380,21866,0,6616,6189,6628,5632,239,6186,6642,4148,6685,0,15362,15362,15394,15350,0,15362,4196,15373,15341,0,22967,21885,22911,20198,622,21863,6671,15391,23059,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,42376,42260,38895,39431,0,38800,12785,31144,21849,0,42227,42415,38770,39500,0,38781,12832,30993,21865,0,38924,38781,38814,35972,0,38919,11341,28065,21876,0,39407,39497,35915,39445,0,35905,11884,31022,20175,0,0,0,0,0,0,0,0,0,0,0,38793,38820,38892,35880,0,38682,11386,27957,21881,0,12825,12802,11375,11882,0,11409,12767,9082,6156,0,31144,30990,28079,31014,0,27941,9118,31087,15334,0,21887,21865,21827,20191,0,21858,6160,15363,21887,0,0,0,0,0,0,0,0,0,0,0,42240,42461,38773,39513,0,38841,12819,30976,21848,0,42455,42325,38767,39476,0,38892,12785,31144,21842,0,38730,38828,38792,35933,0,38756,11368,27906,21877,0,39490,39461,35924,39517,0,36015,11855,31112,20157,0,0,0,0,0,0,0,0,0,0,0,38809,38919,38739,36020,0,38912,11379,28042,21887,0,12801,12818,11361,11830,0,11425,12751,9055,6157,0,30976,31138,27934,31137,0,28015,9104,31044,15364,0,21893,21842,21821,20180,0,21886,6148,15394,21870,0,0,0,0,0,0,0,0,0,0,0,38873,38770,38795,35979,0,38921,11377,28046,21827,0,38781,38814,38784,35930,0,38739,11392,27922,21877,0,38809,38739,38783,36030,0,38767,11343,28073,21863,0,35942,35968,36001,35872,0,35871,10502,27928,20154,0,0,0,0,0,0,0,0,0,0,0,38914,38756,38806,35837,0,38785,11376,28014,21870,0,11372,11380,11370,10453,0,11382,11381,7871,6152,0,28046,27880,28083,27953,0,27997,7918,28043,15331,0,21876,21877,21862,20192,0,21859,6138,15363,21839,0,0,0,0,0,0,0,0,0,0,0,39403,39465,35963,39469,0,35880,11880,31024,20147,0,39499,39478,35933,39536,0,36001,11895,31129,20202,0,35962,35924,35991,35869,0,35825,10453,27941,20198,0,39448,39534,35878,39537,0,36011,11872,31138,20205,0,0,0,0,0,0,0,0,0,0,0,35905,35975,35828,36017,0,35993,10462,27991,20192,0,11895,11890,10502,11850,0,10508,11872,9096,5640,0,31024,31101,27957,31152,0,27959,9114,30987,15330,0,20178,20202,20168,20213,0,20206,5635,15387,20164,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,38792,38812,38914,35872,0,38690,11409,27954,21852,0,38789,38891,38751,36015,0,38873,11386,28032,21917,0,38921,38749,38841,35830,0,38781,11334,27997,21888,0,35866,36020,35837,35997,0,35978,10477,27947,20211,0,0,0,0,0,0,0,0,0,0,0,38695,38915,38748,35939,0,38820,11360,27932,21893,0,11386,11390,11377,10490,0,11401,11375,7874,6188,0,27954,28009,28014,27962,0,27904,7944,27895,15345,0,21871,21917,21878,20198,0,21865,6135,15386,21867,0,0,0,0,0,0,0,0,0,0,0,12750,12801,11401,11884,0,11430,12831,9079,6106,0,12819,12738,11383,11890,0,11336,12754,9104,6138,0,11377,11378,11384,10499,0,11377,11369,7915,6161,0,11882,11895,10508,11861,0,10515,11864,9055,5635,0,0,0,0,0,0,0,0,0,0,0,11430,11372,11334,10518,0,11384,11341,7920,6169,0,12787,12806,11361,11830,0,11401,12774,9056,6160,0,9079,9055,7930,9110,0,7903,9129,9088,4124,0,6189,6138,6116,5640,0,6127,6107,4203,6175,0,0,0,0,0,0,0,0,0,0,0,31144,30990,28079,31014,0,27941,9118,31087,15334,0,30993,31118,27880,31161,0,28006,9110,31034,15381,0,28065,27922,28052,27940,0,27975,7845,28051,15363,0,31022,31148,27925,31149,0,27991,9110,30976,15366,0,0,0,0,0,0,0,0,0,0,0,27957,28031,27985,27959,0,27909,7874,27906,15378,0,9082,9142,7891,9055,0,7944,9077,9059,4174,0,31087,31021,28047,30993,0,27880,9128,31029,15351,0,15363,15381,15331,15362,0,15368,4129,15376,15365,0,0,0,0,0,0,0,0,0,0,0,21857,21848,21857,20175,0,21832,6189,15352,21887,0,21893,21842,21821,20180,0,21886,6148,15394,21870,0,21846,21877,21871,20168,0,21870,6122,15339,21869,0,20163,20157,20198,20225,0,20198,5677,15362,20138,0,0,0,0,0,0,0,0,0,0,0,21869,21887,21859,20211,0,21839,6086,15372,21863,0,6106,6157,6167,5620,0,6170,6148,4124,6125,0,15352,15364,15374,15378,0,15344,4203,15365,15362,0,21907,21870,21826,20155,0,21871,6137,15396,21870,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,40102,38858,40226,35979,958,38812,12128,27909,22937,0,38895,38785,38806,35962,0,38891,11372,28079,21847,0,40265,38795,40347,35913,974,38749,12036,27880,23000,0,35974,35972,35930,36013,0,36020,10503,28052,20170,0,958,0,981,0,962,0,351,0,629,0,38841,38908,38715,36012,0,38915,11336,28015,21910,0,12093,11377,12079,10480,351,11390,12052,7863,6638,0,27909,28034,27906,28050,0,28009,7949,27962,15355,0,22982,21847,22986,20157,633,21917,6608,15372,22948,0,0,0,0,0,0,0,0,0,0,0,38912,38774,38809,35915,0,38938,11401,28037,21833,0,38773,38799,38800,35968,0,38715,11383,27934,21866,0,38767,38793,38820,35987,0,38850,11384,28025,21847,0,35981,35933,36016,35872,0,35837,10508,27954,20168,0,0,0,0,0,0,0,0,0,0,0,38921,38749,38841,35830,0,38781,11334,27997,21888,0,11341,11392,11405,10461,0,11393,11361,7845,6138,0,28037,27901,28073,27925,0,27979,7930,28024,15347,0,21857,21866,21864,20154,0,21876,6116,15374,21893,0,0,0,0,0,0,0,0,0,0,0,40283,38806,40341,35924,974,38751,12075,27895,22986,0,38795,38808,38781,36014,0,38841,11415,28083,21867,0,40329,38809,40427,35866,957,38687,12043,27940,22980,0,35918,36030,35905,35975,0,36017,10540,28028,20198,0,974,0,962,0,929,0,347,0,622,0,38726,38850,38682,35965,0,38828,11369,27959,21907,0,12067,11443,12095,10465,347,11408,12058,7850,6625,0,27895,28039,27941,28032,0,27939,7933,27918,15362,0,23000,21867,22969,20205,622,21887,6605,15362,22948,0,0,0,0,0,0,0,0,0,0,0,35993,35942,35968,36001,0,36012,10511,28063,20181,0,35963,35937,35987,35880,0,35846,10499,27957,20192,0,35933,36016,35872,36001,0,35995,10465,28009,20213,0,35991,35869,36015,35825,0,35876,10513,28011,20184,0,0,0,0,0,0,0,0,0,0,0,36020,35837,35997,35875,0,35915,10449,28051,20197,0,10451,10511,10540,10480,0,10530,10510,7858,5621,0,28063,27928,28015,28002,0,28025,7916,28069,15340,0,20180,20192,20211,20188,0,20178,5626,15362,20178,0,0,0,0,0,0,0,0,0,0,0,958,0,974,0,962,0,351,0,629,0,0,0,0,0,0,0,0,0,0,0,981,0,962,0,929,0,347,0,622,0,0,0,0,0,0,0,0,0,0,0,962,0,929,0,876,0,358,0,611,0,0,0,0,0,0,0,0,0,0,0,351,0,348,0,358,0,378,0,251,0,0,0,0,0,0,0,0,0,0,0,629,0,622,0,609,0,251,0,633,0,0,0,0,0,0,0,0,0,0,0,38820,38892,38726,36017,0,38858,11390,28031,21886,0,38914,38756,38806,35837,0,38785,11376,28014,21870,0,38751,38827,38666,35970,0,38795,11381,27939,21875,0,36011,35830,36011,35891,0,35972,10516,28043,20169,0,0,0,0,0,0,0,0,0,0,0,38922,38773,38799,35942,0,38908,11321,28064,21857,0,11336,11346,11396,10485,0,11377,11378,7869,6107,0,28031,27985,27959,28041,0,28034,7919,28050,15373,0,21906,21870,21885,20158,0,21847,6107,15351,21871,0,0,0,0,0,0,0,0,0,0,0,12108,11341,12093,10503,351,11379,12066,7897,6574,0,11401,11361,11343,10511,0,11350,11358,7930,6167,0,12086,11398,12099,10468,347,11396,12101,7883,6633,0,10480,10499,10506,10498,0,10496,10508,7875,5626,0,351,0,347,0,357,0,378,0,251,0,11386,11382,11381,10479,0,11377,11337,7894,6167,0,12005,11399,12101,10493,378,11392,12133,7869,6642,0,7897,7845,7901,7938,0,7857,7915,7914,4138,0,6646,6167,6600,5621,251,6148,6629,4175,6713,0,0,0,0,0,0,0,0,0,0,0,27909,28034,27906,28050,0,28009,7949,27962,15355,0,28079,27895,28039,27941,0,28011,7871,28047,15372,0,27880,28083,27953,28006,0,27960,7894,27901,15362,0,28052,27940,28042,27975,0,28051,7938,28037,15360,0,0,0,0,0,0,0,0,0,0,0,28015,28002,27968,28025,0,28069,7869,28025,15397,0,7863,7915,7913,7875,0,7919,7906,7873,4127,0,27962,28020,27904,28079,0,28039,7918,28032,15395,0,15372,15372,15362,15331,0,15391,4113,15367,15363,0,0,0,0,0,0,0,0,0,0,0,22948,21833,22995,20178,629,21904,6646,15359,22921,0,21857,21866,21864,20154,0,21876,6116,15374,21893,0,22946,21847,22995,20211,622,21907,6638,15330,22917,0,20202,20168,20213,20190,0,20158,5692,15368,20163,0,633,0,622,0,609,0,251,0,633,0,21892,21888,21887,20169,0,21876,6116,15368,21869,0,6574,6138,6674,5642,251,6160,6703,4138,6631,0,15359,15347,15366,15380,0,15360,4175,15391,15352,0,22918,21893,22909,20147,633,21881,6618,15362,23022,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,39500,39403,35939,39476,0,35987,11883,31144,20157,0,39406,39499,35981,39459,0,35872,11882,31038,20178,0,35973,35962,35924,35991,0,36015,10466,28039,20157,0,39482,39448,36014,39375,0,35830,11901,31029,20175,0,0,0,0,0,0,0,0,0,0,0,36030,35905,35975,35828,0,35875,10480,27979,20200,0,11856,11895,10511,11882,0,10473,11900,9058,5632,0,31144,31024,28025,31039,0,27985,9084,31162,15350,0,20155,20178,20202,20168,0,20190,5624,15339,20198,0,0,0,0,0,0,0,0,0,0,0,39422,39502,35972,39458,0,35866,11901,31046,20178,0,39497,39416,35918,39554,0,35975,11830,31148,20178,0,35942,35968,36001,35872,0,35871,10502,27928,20154,0,39469,39506,35880,39544,0,35965,11896,31152,20211,0,0,0,0,0,0,0,0,0,0,0,35869,36015,35825,35970,0,35976,10478,27939,20198,0,11841,11889,10522,11872,0,10518,11912,9094,5621,0,31046,31138,27940,31161,0,27947,9099,31008,15358,0,20175,20178,20215,20198,0,20192,5620,15366,20191,0,0,0,0,0,0,0,0,0,0,0,35979,35981,35933,36016,0,36001,10511,28050,20202,0,35962,35924,35991,35869,0,35825,10453,27941,20198,0,35913,36014,35878,36011,0,36011,10480,28006,20205,0,36013,35866,36020,35837,0,35875,10526,27975,20190,0,0,0,0,0,0,0,0,0,0,0,36012,35871,36001,35868,0,35963,10485,28025,20182,0,10480,10499,10506,10498,0,10496,10508,7875,5626,0,28050,27954,28009,28014,0,28020,7902,28079,15368,0,20157,20198,20225,20184,0,20190,5607,15331,20191,0,0,0,0,0,0,0,0,0,0,0,39416,39445,36030,39408,0,35828,11908,30997,20215,0,39499,39529,35872,39540,0,36001,11850,31139,20229,0,35987,35880,36017,35846,0,35871,10498,27985,20188,0,39375,39532,35837,39503,0,35973,11895,31043,20206,0,0,0,0,0,0,0,0,0,0,0,35830,36011,35891,35974,0,35930,10493,27901,20173,0,11853,11864,10526,11862,0,10487,11932,9062,5605,0,30997,31149,27979,31067,0,27897,9085,31049,15367,0,20154,20229,20183,20204,0,20202,5633,15344,20180,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,36001,35872,36012,35871,0,35868,10473,28002,20183,0,35880,36017,35846,35965,0,35979,10490,27959,20216,0,36001,35837,35995,35903,0,35962,10482,28020,20158,0,35825,35970,35876,35976,0,35913,10538,27918,20181,0,0,0,0,0,0,0,0,0,0,0,35875,35978,35915,35918,0,35905,10494,27901,20175,0,10480,10462,10530,10510,0,10499,10511,7895,5621,0,28002,27968,28025,27932,0,27897,7893,27957,15365,0,20188,20216,20178,20156,0,20178,5628,15341,20213,0,0,0,0,0,0,0,0,0,0,0,11895,11841,10514,11901,0,10468,11910,9100,5632,0,11901,11888,10461,11864,0,10477,11830,9099,5695,0,10451,10511,10540,10480,0,10530,10510,7858,5621,0,11882,11850,10473,11900,0,10470,11883,9070,5633,0,0,0,0,0,0,0,0,0,0,0,10504,10515,10482,10462,0,10505,10466,7862,5655,0,11869,11869,10538,11895,0,10514,11901,9058,5601,0,9100,9094,7870,9083,0,7869,9046,9150,4181,0,5636,5695,5642,5605,0,5691,5642,4135,5665,0,0,0,0,0,0,0,0,0,0,0,31144,31024,28025,31039,0,27985,9084,31162,15350,0,31038,31129,27954,31124,0,27962,9055,30990,15387,0,28039,27941,28032,28011,0,28047,7910,28046,15331,0,31029,31138,27997,31034,0,27901,9083,31046,15368,0,0,0,0,0,0,0,0,0,0,0,27979,27991,28024,27897,0,27934,7895,27928,15363,0,9058,9096,7916,9070,0,7893,9102,9090,4112,0,31162,30987,28034,31038,0,27954,9082,31088,15369,0,15339,15387,15368,15345,0,15391,4133,15334,15372,0,0,0,0,0,0,0,0,0,0,0,20185,20178,20170,20192,0,20190,5636,15363,20165,0,20175,20178,20215,20198,0,20192,5620,15366,20191,0,20181,20154,20229,20183,0,20182,5683,15340,20147,0,20192,20211,20188,20216,0,20156,5667,15378,20202,0,0,0,0,0,0,0,0,0,0,0,20184,20198,20190,20181,0,20191,5645,15351,20205,0,5632,5621,5652,5681,0,5617,5679,4181,5601,0,15363,15358,15360,15372,0,15382,4135,15371,15359,0,20160,20191,20175,20181,0,20229,5626,15364,20182};

bool check(ll x){
    ll y = x;
    while(y > 0){
        ll digit = y % 10;
        y /= 10;
        if(digit == 0) return false;
        if(x % digit != 0) return false;
    }
    return true;
}

ll f(ll x){
    ll ans = 0;
    ll idx = x / 10000000;
    idx = min(idx, ll(5000));
    for(ll i=idx*10000000+1; i<=x; i++){
        if(check(i))
            ans++;
    }
    for(int i=0; i<=idx; i++)
        ans += tab[i];
    return ans;
}

int main(){	
	BOOST;

    ll p, q;
    cin>> p >> q;
    cout<< f(q) - f(p-1);

	
	return 0;
}