PY01032-SOTHUANNGHICH.py

from math import *
from functools import cmp_to_key
import re


def checkPal(s):
    l = 0
    r = len(s) - 1
    while l < r:
        if s[l] != s[r]: return 0
        l += 1
        r -= 1
    return 1


def cs(n, k):
    s = ""
    while n:
        s = str(n % k) + s
        n //= k
    return checkPal(s)


def NumOfAns(a, b, m):
    cnt = 0
    for i in range(a, b + 1):
        check = 1
        for k in range(2, m + 1):
            if cs(i, k) == 0:
                check = 0
                break
        if check:
            cnt += 1
    return cnt


def main():
    a, b, m = map(int, input().split())
    if (m == 2):
        l = [0] * 2000001
        l[0] = 1
        l[1] = 1
        l[3] = 1
        l[5] = 1
        l[7] = 1
        l[9] = 1
        l[15] = 1
        l[17] = 1
        l[21] = 1
        l[27] = 1
        l[31] = 1
        l[33] = 1
        l[45] = 1
        l[51] = 1
        l[63] = 1
        l[65] = 1
        l[73] = 1
        l[85] = 1
        l[93] = 1
        l[99] = 1
        l[107] = 1
        l[119] = 1
        l[127] = 1
        l[129] = 1
        l[153] = 1
        l[165] = 1
        l[189] = 1
        l[195] = 1
        l[219] = 1
        l[231] = 1
        l[255] = 1
        l[257] = 1
        l[273] = 1
        l[297] = 1
        l[313] = 1
        l[325] = 1
        l[341] = 1
        l[365] = 1
        l[381] = 1
        l[387] = 1
        l[403] = 1
        l[427] = 1
        l[443] = 1
        l[455] = 1
        l[471] = 1
        l[495] = 1
        l[511] = 1
        l[513] = 1
        l[561] = 1
        l[585] = 1
        l[633] = 1
        l[645] = 1
        l[693] = 1
        l[717] = 1
        l[765] = 1
        l[771] = 1
        l[819] = 1
        l[843] = 1
        l[891] = 1
        l[903] = 1
        l[951] = 1
        l[975] = 1
        l[1023] = 1
        l[1025] = 1
        l[1057] = 1
        l[1105] = 1
        l[1137] = 1
        l[1161] = 1
        l[1193] = 1
        l[1241] = 1
        l[1273] = 1
        l[1285] = 1
        l[1317] = 1
        l[1365] = 1
        l[1397] = 1
        l[1421] = 1
        l[1453] = 1
        l[1501] = 1
        l[1533] = 1
        l[1539] = 1
        l[1571] = 1
        l[1619] = 1
        l[1651] = 1
        l[1675] = 1
        l[1707] = 1
        l[1755] = 1
        l[1787] = 1
        l[1799] = 1
        l[1831] = 1
        l[1879] = 1
        l[1911] = 1
        l[1935] = 1
        l[1967] = 1
        l[2015] = 1
        l[2047] = 1
        l[2049] = 1
        l[2145] = 1
        l[2193] = 1
        l[2289] = 1
        l[2313] = 1
        l[2409] = 1
        l[2457] = 1
        l[2553] = 1
        l[2565] = 1
        l[2661] = 1
        l[2709] = 1
        l[2805] = 1
        l[2829] = 1
        l[2925] = 1
        l[2973] = 1
        l[3069] = 1
        l[3075] = 1
        l[3171] = 1
        l[3219] = 1
        l[3315] = 1
        l[3339] = 1
        l[3435] = 1
        l[3483] = 1
        l[3579] = 1
        l[3591] = 1
        l[3687] = 1
        l[3735] = 1
        l[3831] = 1
        l[3855] = 1
        l[3951] = 1
        l[3999] = 1
        l[4095] = 1
        l[4097] = 1
        l[4161] = 1
        l[4257] = 1
        l[4321] = 1
        l[4369] = 1
        l[4433] = 1
        l[4529] = 1
        l[4593] = 1
        l[4617] = 1
        l[4681] = 1
        l[4777] = 1
        l[4841] = 1
        l[4889] = 1
        l[4953] = 1
        l[5049] = 1
        l[5113] = 1
        l[5125] = 1
        l[5189] = 1
        l[5285] = 1
        l[5349] = 1
        l[5397] = 1
        l[5461] = 1
        l[5557] = 1
        l[5621] = 1
        l[5645] = 1
        l[5709] = 1
        l[5805] = 1
        l[5869] = 1
        l[5917] = 1
        l[5981] = 1
        l[6077] = 1
        l[6141] = 1
        l[6147] = 1
        l[6211] = 1
        l[6307] = 1
        l[6371] = 1
        l[6419] = 1
        l[6483] = 1
        l[6579] = 1
        l[6643] = 1
        l[6667] = 1
        l[6731] = 1
        l[6827] = 1
        l[6891] = 1
        l[6939] = 1
        l[7003] = 1
        l[7099] = 1
        l[7163] = 1
        l[7175] = 1
        l[7239] = 1
        l[7335] = 1
        l[7399] = 1
        l[7447] = 1
        l[7511] = 1
        l[7607] = 1
        l[7671] = 1
        l[7695] = 1
        l[7759] = 1
        l[7855] = 1
        l[7919] = 1
        l[7967] = 1
        l[8031] = 1
        l[8127] = 1
        l[8191] = 1
        l[8193] = 1
        l[8385] = 1
        l[8481] = 1
        l[8673] = 1
        l[8721] = 1
        l[8913] = 1
        l[9009] = 1
        l[9201] = 1
        l[9225] = 1
        l[9417] = 1
        l[9513] = 1
        l[9705] = 1
        l[9753] = 1
        l[9945] = 1
        l[10041] = 1
        l[10233] = 1
        l[10245] = 1
        l[10437] = 1
        l[10533] = 1
        l[10725] = 1
        l[10773] = 1
        l[10965] = 1
        l[11061] = 1
        l[11253] = 1
        l[11277] = 1
        l[11469] = 1
        l[11565] = 1
        l[11757] = 1
        l[11805] = 1
        l[11997] = 1
        l[12093] = 1
        l[12285] = 1
        l[12291] = 1
        l[12483] = 1
        l[12579] = 1
        l[12771] = 1
        l[12819] = 1
        l[13011] = 1
        l[13107] = 1
        l[13299] = 1
        l[13323] = 1
        l[13515] = 1
        l[13611] = 1
        l[13803] = 1
        l[13851] = 1
        l[14043] = 1
        l[14139] = 1
        l[14331] = 1
        l[14343] = 1
        l[14535] = 1
        l[14631] = 1
        l[14823] = 1
        l[14871] = 1
        l[15063] = 1
        l[15159] = 1
        l[15351] = 1
        l[15375] = 1
        l[15567] = 1
        l[15663] = 1
        l[15855] = 1
        l[15903] = 1
        l[16095] = 1
        l[16191] = 1
        l[16383] = 1
        l[16385] = 1
        l[16513] = 1
        l[16705] = 1
        l[16833] = 1
        l[16929] = 1
        l[17057] = 1
        l[17249] = 1
        l[17377] = 1
        l[17425] = 1
        l[17553] = 1
        l[17745] = 1
        l[17873] = 1
        l[17969] = 1
        l[18097] = 1
        l[18289] = 1
        l[18417] = 1
        l[18441] = 1
        l[18569] = 1
        l[18761] = 1
        l[18889] = 1
        l[18985] = 1
        l[19113] = 1
        l[19305] = 1
        l[19433] = 1
        l[19481] = 1
        l[19609] = 1
        l[19801] = 1
        l[19929] = 1
        l[20025] = 1
        l[20153] = 1
        l[20345] = 1
        l[20473] = 1
        l[20485] = 1
        l[20613] = 1
        l[20805] = 1
        l[20933] = 1
        l[21029] = 1
        l[21157] = 1
        l[21349] = 1
        l[21477] = 1
        l[21525] = 1
        l[21653] = 1
        l[21845] = 1
        l[21973] = 1
        l[22069] = 1
        l[22197] = 1
        l[22389] = 1
        l[22517] = 1
        l[22541] = 1
        l[22669] = 1
        l[22861] = 1
        l[22989] = 1
        l[23085] = 1
        l[23213] = 1
        l[23405] = 1
        l[23533] = 1
        l[23581] = 1
        l[23709] = 1
        l[23901] = 1
        l[24029] = 1
        l[24125] = 1
        l[24253] = 1
        l[24445] = 1
        l[24573] = 1
        l[24579] = 1
        l[24707] = 1
        l[24899] = 1
        l[25027] = 1
        l[25123] = 1
        l[25251] = 1
        l[25443] = 1
        l[25571] = 1
        l[25619] = 1
        l[25747] = 1
        l[25939] = 1
        l[26067] = 1
        l[26163] = 1
        l[26291] = 1
        l[26483] = 1
        l[26611] = 1
        l[26635] = 1
        l[26763] = 1
        l[26955] = 1
        l[27083] = 1
        l[27179] = 1
        l[27307] = 1
        l[27499] = 1
        l[27627] = 1
        l[27675] = 1
        l[27803] = 1
        l[27995] = 1
        l[28123] = 1
        l[28219] = 1
        l[28347] = 1
        l[28539] = 1
        l[28667] = 1
        l[28679] = 1
        l[28807] = 1
        l[28999] = 1
        l[29127] = 1
        l[29223] = 1
        l[29351] = 1
        l[29543] = 1
        l[29671] = 1
        l[29719] = 1
        l[29847] = 1
        l[30039] = 1
        l[30167] = 1
        l[30263] = 1
        l[30391] = 1
        l[30583] = 1
        l[30711] = 1
        l[30735] = 1
        l[30863] = 1
        l[31055] = 1
        l[31183] = 1
        l[31279] = 1
        l[31407] = 1
        l[31599] = 1
        l[31727] = 1
        l[31775] = 1
        l[31903] = 1
        l[32095] = 1
        l[32223] = 1
        l[32319] = 1
        l[32447] = 1
        l[32639] = 1
        l[32767] = 1
        l[32769] = 1
        l[33153] = 1
        l[33345] = 1
        l[33729] = 1
        l[33825] = 1
        l[34209] = 1
        l[34401] = 1
        l[34785] = 1
        l[34833] = 1
        l[35217] = 1
        l[35409] = 1
        l[35793] = 1
        l[35889] = 1
        l[36273] = 1
        l[36465] = 1
        l[36849] = 1
        l[36873] = 1
        l[37257] = 1
        l[37449] = 1
        l[37833] = 1
        l[37929] = 1
        l[38313] = 1
        l[38505] = 1
        l[38889] = 1
        l[38937] = 1
        l[39321] = 1
        l[39513] = 1
        l[39897] = 1
        l[39993] = 1
        l[40377] = 1
        l[40569] = 1
        l[40953] = 1
        l[40965] = 1
        l[41349] = 1
        l[41541] = 1
        l[41925] = 1
        l[42021] = 1
        l[42405] = 1
        l[42597] = 1
        l[42981] = 1
        l[43029] = 1
        l[43413] = 1
        l[43605] = 1
        l[43989] = 1
        l[44085] = 1
        l[44469] = 1
        l[44661] = 1
        l[45045] = 1
        l[45069] = 1
        l[45453] = 1
        l[45645] = 1
        l[46029] = 1
        l[46125] = 1
        l[46509] = 1
        l[46701] = 1
        l[47085] = 1
        l[47133] = 1
        l[47517] = 1
        l[47709] = 1
        l[48093] = 1
        l[48189] = 1
        l[48573] = 1
        l[48765] = 1
        l[49149] = 1
        l[49155] = 1
        l[49539] = 1
        l[49731] = 1
        l[50115] = 1
        l[50211] = 1
        l[50595] = 1
        l[50787] = 1
        l[51171] = 1
        l[51219] = 1
        l[51603] = 1
        l[51795] = 1
        l[52179] = 1
        l[52275] = 1
        l[52659] = 1
        l[52851] = 1
        l[53235] = 1
        l[53259] = 1
        l[53643] = 1
        l[53835] = 1
        l[54219] = 1
        l[54315] = 1
        l[54699] = 1
        l[54891] = 1
        l[55275] = 1
        l[55323] = 1
        l[55707] = 1
        l[55899] = 1
        l[56283] = 1
        l[56379] = 1
        l[56763] = 1
        l[56955] = 1
        l[57339] = 1
        l[57351] = 1
        l[57735] = 1
        l[57927] = 1
        l[58311] = 1
        l[58407] = 1
        l[58791] = 1
        l[58983] = 1
        l[59367] = 1
        l[59415] = 1
        l[59799] = 1
        l[59991] = 1
        l[60375] = 1
        l[60471] = 1
        l[60855] = 1
        l[61047] = 1
        l[61431] = 1
        l[61455] = 1
        l[61839] = 1
        l[62031] = 1
        l[62415] = 1
        l[62511] = 1
        l[62895] = 1
        l[63087] = 1
        l[63471] = 1
        l[63519] = 1
        l[63903] = 1
        l[64095] = 1
        l[64479] = 1
        l[64575] = 1
        l[64959] = 1
        l[65151] = 1
        l[65535] = 1
        l[65537] = 1
        l[65793] = 1
        l[66177] = 1
        l[66433] = 1
        l[66625] = 1
        l[66881] = 1
        l[67265] = 1
        l[67521] = 1
        l[67617] = 1
        l[67873] = 1
        l[68257] = 1
        l[68513] = 1
        l[68705] = 1
        l[68961] = 1
        l[69345] = 1
        l[69601] = 1
        l[69649] = 1
        l[69905] = 1
        l[70289] = 1
        l[70545] = 1
        l[70737] = 1
        l[70993] = 1
        l[71377] = 1
        l[71633] = 1
        l[71729] = 1
        l[71985] = 1
        l[72369] = 1
        l[72625] = 1
        l[72817] = 1
        l[73073] = 1
        l[73457] = 1
        l[73713] = 1
        l[73737] = 1
        l[73993] = 1
        l[74377] = 1
        l[74633] = 1
        l[74825] = 1
        l[75081] = 1
        l[75465] = 1
        l[75721] = 1
        l[75817] = 1
        l[76073] = 1
        l[76457] = 1
        l[76713] = 1
        l[76905] = 1
        l[77161] = 1
        l[77545] = 1
        l[77801] = 1
        l[77849] = 1
        l[78105] = 1
        l[78489] = 1
        l[78745] = 1
        l[78937] = 1
        l[79193] = 1
        l[79577] = 1
        l[79833] = 1
        l[79929] = 1
        l[80185] = 1
        l[80569] = 1
        l[80825] = 1
        l[81017] = 1
        l[81273] = 1
        l[81657] = 1
        l[81913] = 1
        l[81925] = 1
        l[82181] = 1
        l[82565] = 1
        l[82821] = 1
        l[83013] = 1
        l[83269] = 1
        l[83653] = 1
        l[83909] = 1
        l[84005] = 1
        l[84261] = 1
        l[84645] = 1
        l[84901] = 1
        l[85093] = 1
        l[85349] = 1
        l[85733] = 1
        l[85989] = 1
        l[86037] = 1
        l[86293] = 1
        l[86677] = 1
        l[86933] = 1
        l[87125] = 1
        l[87381] = 1
        l[87765] = 1
        l[88021] = 1
        l[88117] = 1
        l[88373] = 1
        l[88757] = 1
        l[89013] = 1
        l[89205] = 1
        l[89461] = 1
        l[89845] = 1
        l[90101] = 1
        l[90125] = 1
        l[90381] = 1
        l[90765] = 1
        l[91021] = 1
        l[91213] = 1
        l[91469] = 1
        l[91853] = 1
        l[92109] = 1
        l[92205] = 1
        l[92461] = 1
        l[92845] = 1
        l[93101] = 1
        l[93293] = 1
        l[93549] = 1
        l[93933] = 1
        l[94189] = 1
        l[94237] = 1
        l[94493] = 1
        l[94877] = 1
        l[95133] = 1
        l[95325] = 1
        l[95581] = 1
        l[95965] = 1
        l[96221] = 1
        l[96317] = 1
        l[96573] = 1
        l[96957] = 1
        l[97213] = 1
        l[97405] = 1
        l[97661] = 1
        l[98045] = 1
        l[98301] = 1
        l[98307] = 1
        l[98563] = 1
        l[98947] = 1
        l[99203] = 1
        l[99395] = 1
        l[99651] = 1
        l[100035] = 1
        l[100291] = 1
        l[100387] = 1
        l[100643] = 1
        l[101027] = 1
        l[101283] = 1
        l[101475] = 1
        l[101731] = 1
        l[102115] = 1
        l[102371] = 1
        l[102419] = 1
        l[102675] = 1
        l[103059] = 1
        l[103315] = 1
        l[103507] = 1
        l[103763] = 1
        l[104147] = 1
        l[104403] = 1
        l[104499] = 1
        l[104755] = 1
        l[105139] = 1
        l[105395] = 1
        l[105587] = 1
        l[105843] = 1
        l[106227] = 1
        l[106483] = 1
        l[106507] = 1
        l[106763] = 1
        l[107147] = 1
        l[107403] = 1
        l[107595] = 1
        l[107851] = 1
        l[108235] = 1
        l[108491] = 1
        l[108587] = 1
        l[108843] = 1
        l[109227] = 1
        l[109483] = 1
        l[109675] = 1
        l[109931] = 1
        l[110315] = 1
        l[110571] = 1
        l[110619] = 1
        l[110875] = 1
        l[111259] = 1
        l[111515] = 1
        l[111707] = 1
        l[111963] = 1
        l[112347] = 1
        l[112603] = 1
        l[112699] = 1
        l[112955] = 1
        l[113339] = 1
        l[113595] = 1
        l[113787] = 1
        l[114043] = 1
        l[114427] = 1
        l[114683] = 1
        l[114695] = 1
        l[114951] = 1
        l[115335] = 1
        l[115591] = 1
        l[115783] = 1
        l[116039] = 1
        l[116423] = 1
        l[116679] = 1
        l[116775] = 1
        l[117031] = 1
        l[117415] = 1
        l[117671] = 1
        l[117863] = 1
        l[118119] = 1
        l[118503] = 1
        l[118759] = 1
        l[118807] = 1
        l[119063] = 1
        l[119447] = 1
        l[119703] = 1
        l[119895] = 1
        l[120151] = 1
        l[120535] = 1
        l[120791] = 1
        l[120887] = 1
        l[121143] = 1
        l[121527] = 1
        l[121783] = 1
        l[121975] = 1
        l[122231] = 1
        l[122615] = 1
        l[122871] = 1
        l[122895] = 1
        l[123151] = 1
        l[123535] = 1
        l[123791] = 1
        l[123983] = 1
        l[124239] = 1
        l[124623] = 1
        l[124879] = 1
        l[124975] = 1
        l[125231] = 1
        l[125615] = 1
        l[125871] = 1
        l[126063] = 1
        l[126319] = 1
        l[126703] = 1
        l[126959] = 1
        l[127007] = 1
        l[127263] = 1
        l[127647] = 1
        l[127903] = 1
        l[128095] = 1
        l[128351] = 1
        l[128735] = 1
        l[128991] = 1
        l[129087] = 1
        l[129343] = 1
        l[129727] = 1
        l[129983] = 1
        l[130175] = 1
        l[130431] = 1
        l[130815] = 1
        l[131071] = 1
        l[131073] = 1
        l[131841] = 1
        l[132225] = 1
        l[132993] = 1
        l[133185] = 1
        l[133953] = 1
        l[134337] = 1
        l[135105] = 1
        l[135201] = 1
        l[135969] = 1
        l[136353] = 1
        l[137121] = 1
        l[137313] = 1
        l[138081] = 1
        l[138465] = 1
        l[139233] = 1
        l[139281] = 1
        l[140049] = 1
        l[140433] = 1
        l[141201] = 1
        l[141393] = 1
        l[142161] = 1
        l[142545] = 1
        l[143313] = 1
        l[143409] = 1
        l[144177] = 1
        l[144561] = 1
        l[145329] = 1
        l[145521] = 1
        l[146289] = 1
        l[146673] = 1
        l[147441] = 1
        l[147465] = 1
        l[148233] = 1
        l[148617] = 1
        l[149385] = 1
        l[149577] = 1
        l[150345] = 1
        l[150729] = 1
        l[151497] = 1
        l[151593] = 1
        l[152361] = 1
        l[152745] = 1
        l[153513] = 1
        l[153705] = 1
        l[154473] = 1
        l[154857] = 1
        l[155625] = 1
        l[155673] = 1
        l[156441] = 1
        l[156825] = 1
        l[157593] = 1
        l[157785] = 1
        l[158553] = 1
        l[158937] = 1
        l[159705] = 1
        l[159801] = 1
        l[160569] = 1
        l[160953] = 1
        l[161721] = 1
        l[161913] = 1
        l[162681] = 1
        l[163065] = 1
        l[163833] = 1
        l[163845] = 1
        l[164613] = 1
        l[164997] = 1
        l[165765] = 1
        l[165957] = 1
        l[166725] = 1
        l[167109] = 1
        l[167877] = 1
        l[167973] = 1
        l[168741] = 1
        l[169125] = 1
        l[169893] = 1
        l[170085] = 1
        l[170853] = 1
        l[171237] = 1
        l[172005] = 1
        l[172053] = 1
        l[172821] = 1
        l[173205] = 1
        l[173973] = 1
        l[174165] = 1
        l[174933] = 1
        l[175317] = 1
        l[176085] = 1
        l[176181] = 1
        l[176949] = 1
        l[177333] = 1
        l[178101] = 1
        l[178293] = 1
        l[179061] = 1
        l[179445] = 1
        l[180213] = 1
        l[180237] = 1
        l[181005] = 1
        l[181389] = 1
        l[182157] = 1
        l[182349] = 1
        l[183117] = 1
        l[183501] = 1
        l[184269] = 1
        l[184365] = 1
        l[185133] = 1
        l[185517] = 1
        l[186285] = 1
        l[186477] = 1
        l[187245] = 1
        l[187629] = 1
        l[188397] = 1
        l[188445] = 1
        l[189213] = 1
        l[189597] = 1
        l[190365] = 1
        l[190557] = 1
        l[191325] = 1
        l[191709] = 1
        l[192477] = 1
        l[192573] = 1
        l[193341] = 1
        l[193725] = 1
        l[194493] = 1
        l[194685] = 1
        l[195453] = 1
        l[195837] = 1
        l[196605] = 1
        l[196611] = 1
        l[197379] = 1
        l[197763] = 1
        l[198531] = 1
        l[198723] = 1
        l[199491] = 1
        l[199875] = 1
        l[200643] = 1
        l[200739] = 1
        l[201507] = 1
        l[201891] = 1
        l[202659] = 1
        l[202851] = 1
        l[203619] = 1
        l[204003] = 1
        l[204771] = 1
        l[204819] = 1
        l[205587] = 1
        l[205971] = 1
        l[206739] = 1
        l[206931] = 1
        l[207699] = 1
        l[208083] = 1
        l[208851] = 1
        l[208947] = 1
        l[209715] = 1
        l[210099] = 1
        l[210867] = 1
        l[211059] = 1
        l[211827] = 1
        l[212211] = 1
        l[212979] = 1
        l[213003] = 1
        l[213771] = 1
        l[214155] = 1
        l[214923] = 1
        l[215115] = 1
        l[215883] = 1
        l[216267] = 1
        l[217035] = 1
        l[217131] = 1
        l[217899] = 1
        l[218283] = 1
        l[219051] = 1
        l[219243] = 1
        l[220011] = 1
        l[220395] = 1
        l[221163] = 1
        l[221211] = 1
        l[221979] = 1
        l[222363] = 1
        l[223131] = 1
        l[223323] = 1
        l[224091] = 1
        l[224475] = 1
        l[225243] = 1
        l[225339] = 1
        l[226107] = 1
        l[226491] = 1
        l[227259] = 1
        l[227451] = 1
        l[228219] = 1
        l[228603] = 1
        l[229371] = 1
        l[229383] = 1
        l[230151] = 1
        l[230535] = 1
        l[231303] = 1
        l[231495] = 1
        l[232263] = 1
        l[232647] = 1
        l[233415] = 1
        l[233511] = 1
        l[234279] = 1
        l[234663] = 1
        l[235431] = 1
        l[235623] = 1
        l[236391] = 1
        l[236775] = 1
        l[237543] = 1
        l[237591] = 1
        l[238359] = 1
        l[238743] = 1
        l[239511] = 1
        l[239703] = 1
        l[240471] = 1
        l[240855] = 1
        l[241623] = 1
        l[241719] = 1
        l[242487] = 1
        l[242871] = 1
        l[243639] = 1
        l[243831] = 1
        l[244599] = 1
        l[244983] = 1
        l[245751] = 1
        l[245775] = 1
        l[246543] = 1
        l[246927] = 1
        l[247695] = 1
        l[247887] = 1
        l[248655] = 1
        l[249039] = 1
        l[249807] = 1
        l[249903] = 1
        l[250671] = 1
        l[251055] = 1
        l[251823] = 1
        l[252015] = 1
        l[252783] = 1
        l[253167] = 1
        l[253935] = 1
        l[253983] = 1
        l[254751] = 1
        l[255135] = 1
        l[255903] = 1
        l[256095] = 1
        l[256863] = 1
        l[257247] = 1
        l[258015] = 1
        l[258111] = 1
        l[258879] = 1
        l[259263] = 1
        l[260031] = 1
        l[260223] = 1
        l[260991] = 1
        l[261375] = 1
        l[262143] = 1
        l[262145] = 1
        l[262657] = 1
        l[263425] = 1
        l[263937] = 1
        l[264321] = 1
        l[264833] = 1
        l[265601] = 1
        l[266113] = 1
        l[266305] = 1
        l[266817] = 1
        l[267585] = 1
        l[268097] = 1
        l[268481] = 1
        l[268993] = 1
        l[269761] = 1
        l[270273] = 1
        l[270369] = 1
        l[270881] = 1
        l[271649] = 1
        l[272161] = 1
        l[272545] = 1
        l[273057] = 1
        l[273825] = 1
        l[274337] = 1
        l[274529] = 1
        l[275041] = 1
        l[275809] = 1
        l[276321] = 1
        l[276705] = 1
        l[277217] = 1
        l[277985] = 1
        l[278497] = 1
        l[278545] = 1
        l[279057] = 1
        l[279825] = 1
        l[280337] = 1
        l[280721] = 1
        l[281233] = 1
        l[282001] = 1
        l[282513] = 1
        l[282705] = 1
        l[283217] = 1
        l[283985] = 1
        l[284497] = 1
        l[284881] = 1
        l[285393] = 1
        l[286161] = 1
        l[286673] = 1
        l[286769] = 1
        l[287281] = 1
        l[288049] = 1
        l[288561] = 1
        l[288945] = 1
        l[289457] = 1
        l[290225] = 1
        l[290737] = 1
        l[290929] = 1
        l[291441] = 1
        l[292209] = 1
        l[292721] = 1
        l[293105] = 1
        l[293617] = 1
        l[294385] = 1
        l[294897] = 1
        l[294921] = 1
        l[295433] = 1
        l[296201] = 1
        l[296713] = 1
        l[297097] = 1
        l[297609] = 1
        l[298377] = 1
        l[298889] = 1
        l[299081] = 1
        l[299593] = 1
        l[300361] = 1
        l[300873] = 1
        l[301257] = 1
        l[301769] = 1
        l[302537] = 1
        l[303049] = 1
        l[303145] = 1
        l[303657] = 1
        l[304425] = 1
        l[304937] = 1
        l[305321] = 1
        l[305833] = 1
        l[306601] = 1
        l[307113] = 1
        l[307305] = 1
        l[307817] = 1
        l[308585] = 1
        l[309097] = 1
        l[309481] = 1
        l[309993] = 1
        l[310761] = 1
        l[311273] = 1
        l[311321] = 1
        l[311833] = 1
        l[312601] = 1
        l[313113] = 1
        l[313497] = 1
        l[314009] = 1
        l[314777] = 1
        l[315289] = 1
        l[315481] = 1
        l[315993] = 1
        l[316761] = 1
        l[317273] = 1
        l[317657] = 1
        l[318169] = 1
        l[318937] = 1
        l[319449] = 1
        l[319545] = 1
        l[320057] = 1
        l[320825] = 1
        l[321337] = 1
        l[321721] = 1
        l[322233] = 1
        l[323001] = 1
        l[323513] = 1
        l[323705] = 1
        l[324217] = 1
        l[324985] = 1
        l[325497] = 1
        l[325881] = 1
        l[326393] = 1
        l[327161] = 1
        l[327673] = 1
        l[327685] = 1
        l[328197] = 1
        l[328965] = 1
        l[329477] = 1
        l[329861] = 1
        l[330373] = 1
        l[331141] = 1
        l[331653] = 1
        l[331845] = 1
        l[332357] = 1
        l[333125] = 1
        l[333637] = 1
        l[334021] = 1
        l[334533] = 1
        l[335301] = 1
        l[335813] = 1
        l[335909] = 1
        l[336421] = 1
        l[337189] = 1
        l[337701] = 1
        l[338085] = 1
        l[338597] = 1
        l[339365] = 1
        l[339877] = 1
        l[340069] = 1
        l[340581] = 1
        l[341349] = 1
        l[341861] = 1
        l[342245] = 1
        l[342757] = 1
        l[343525] = 1
        l[344037] = 1
        l[344085] = 1
        l[344597] = 1
        l[345365] = 1
        l[345877] = 1
        l[346261] = 1
        l[346773] = 1
        l[347541] = 1
        l[348053] = 1
        l[348245] = 1
        l[348757] = 1
        l[349525] = 1
        l[350037] = 1
        l[350421] = 1
        l[350933] = 1
        l[351701] = 1
        l[352213] = 1
        l[352309] = 1
        l[352821] = 1
        l[353589] = 1
        l[354101] = 1
        l[354485] = 1
        l[354997] = 1
        l[355765] = 1
        l[356277] = 1
        l[356469] = 1
        l[356981] = 1
        l[357749] = 1
        l[358261] = 1
        l[358645] = 1
        l[359157] = 1
        l[359925] = 1
        l[360437] = 1
        l[360461] = 1
        l[360973] = 1
        l[361741] = 1
        l[362253] = 1
        l[362637] = 1
        l[363149] = 1
        l[363917] = 1
        l[364429] = 1
        l[364621] = 1
        l[365133] = 1
        l[365901] = 1
        l[366413] = 1
        l[366797] = 1
        l[367309] = 1
        l[368077] = 1
        l[368589] = 1
        l[368685] = 1
        l[369197] = 1
        l[369965] = 1
        l[370477] = 1
        l[370861] = 1
        l[371373] = 1
        l[372141] = 1
        l[372653] = 1
        l[372845] = 1
        l[373357] = 1
        l[374125] = 1
        l[374637] = 1
        l[375021] = 1
        l[375533] = 1
        l[376301] = 1
        l[376813] = 1
        l[376861] = 1
        l[377373] = 1
        l[378141] = 1
        l[378653] = 1
        l[379037] = 1
        l[379549] = 1
        l[380317] = 1
        l[380829] = 1
        l[381021] = 1
        l[381533] = 1
        l[382301] = 1
        l[382813] = 1
        l[383197] = 1
        l[383709] = 1
        l[384477] = 1
        l[384989] = 1
        l[385085] = 1
        l[385597] = 1
        l[386365] = 1
        l[386877] = 1
        l[387261] = 1
        l[387773] = 1
        l[388541] = 1
        l[389053] = 1
        l[389245] = 1
        l[389757] = 1
        l[390525] = 1
        l[391037] = 1
        l[391421] = 1
        l[391933] = 1
        l[392701] = 1
        l[393213] = 1
        l[393219] = 1
        l[393731] = 1
        l[394499] = 1
        l[395011] = 1
        l[395395] = 1
        l[395907] = 1
        l[396675] = 1
        l[397187] = 1
        l[397379] = 1
        l[397891] = 1
        l[398659] = 1
        l[399171] = 1
        l[399555] = 1
        l[400067] = 1
        l[400835] = 1
        l[401347] = 1
        l[401443] = 1
        l[401955] = 1
        l[402723] = 1
        l[403235] = 1
        l[403619] = 1
        l[404131] = 1
        l[404899] = 1
        l[405411] = 1
        l[405603] = 1
        l[406115] = 1
        l[406883] = 1
        l[407395] = 1
        l[407779] = 1
        l[408291] = 1
        l[409059] = 1
        l[409571] = 1
        l[409619] = 1
        l[410131] = 1
        l[410899] = 1
        l[411411] = 1
        l[411795] = 1
        l[412307] = 1
        l[413075] = 1
        l[413587] = 1
        l[413779] = 1
        l[414291] = 1
        l[415059] = 1
        l[415571] = 1
        l[415955] = 1
        l[416467] = 1
        l[417235] = 1
        l[417747] = 1
        l[417843] = 1
        l[418355] = 1
        l[419123] = 1
        l[419635] = 1
        l[420019] = 1
        l[420531] = 1
        l[421299] = 1
        l[421811] = 1
        l[422003] = 1
        l[422515] = 1
        l[423283] = 1
        l[423795] = 1
        l[424179] = 1
        l[424691] = 1
        l[425459] = 1
        l[425971] = 1
        l[425995] = 1
        l[426507] = 1
        l[427275] = 1
        l[427787] = 1
        l[428171] = 1
        l[428683] = 1
        l[429451] = 1
        l[429963] = 1
        l[430155] = 1
        l[430667] = 1
        l[431435] = 1
        l[431947] = 1
        l[432331] = 1
        l[432843] = 1
        l[433611] = 1
        l[434123] = 1
        l[434219] = 1
        l[434731] = 1
        l[435499] = 1
        l[436011] = 1
        l[436395] = 1
        l[436907] = 1
        l[437675] = 1
        l[438187] = 1
        l[438379] = 1
        l[438891] = 1
        l[439659] = 1
        l[440171] = 1
        l[440555] = 1
        l[441067] = 1
        l[441835] = 1
        l[442347] = 1
        l[442395] = 1
        l[442907] = 1
        l[443675] = 1
        l[444187] = 1
        l[444571] = 1
        l[445083] = 1
        l[445851] = 1
        l[446363] = 1
        l[446555] = 1
        l[447067] = 1
        l[447835] = 1
        l[448347] = 1
        l[448731] = 1
        l[449243] = 1
        l[450011] = 1
        l[450523] = 1
        l[450619] = 1
        l[451131] = 1
        l[451899] = 1
        l[452411] = 1
        l[452795] = 1
        l[453307] = 1
        l[454075] = 1
        l[454587] = 1
        l[454779] = 1
        l[455291] = 1
        l[456059] = 1
        l[456571] = 1
        l[456955] = 1
        l[457467] = 1
        l[458235] = 1
        l[458747] = 1
        l[458759] = 1
        l[459271] = 1
        l[460039] = 1
        l[460551] = 1
        l[460935] = 1
        l[461447] = 1
        l[462215] = 1
        l[462727] = 1
        l[462919] = 1
        l[463431] = 1
        l[464199] = 1
        l[464711] = 1
        l[465095] = 1
        l[465607] = 1
        l[466375] = 1
        l[466887] = 1
        l[466983] = 1
        l[467495] = 1
        l[468263] = 1
        l[468775] = 1
        l[469159] = 1
        l[469671] = 1
        l[470439] = 1
        l[470951] = 1
        l[471143] = 1
        l[471655] = 1
        l[472423] = 1
        l[472935] = 1
        l[473319] = 1
        l[473831] = 1
        l[474599] = 1
        l[475111] = 1
        l[475159] = 1
        l[475671] = 1
        l[476439] = 1
        l[476951] = 1
        l[477335] = 1
        l[477847] = 1
        l[478615] = 1
        l[479127] = 1
        l[479319] = 1
        l[479831] = 1
        l[480599] = 1
        l[481111] = 1
        l[481495] = 1
        l[482007] = 1
        l[482775] = 1
        l[483287] = 1
        l[483383] = 1
        l[483895] = 1
        l[484663] = 1
        l[485175] = 1
        l[485559] = 1
        l[486071] = 1
        l[486839] = 1
        l[487351] = 1
        l[487543] = 1
        l[488055] = 1
        l[488823] = 1
        l[489335] = 1
        l[489719] = 1
        l[490231] = 1
        l[490999] = 1
        l[491511] = 1
        l[491535] = 1
        l[492047] = 1
        l[492815] = 1
        l[493327] = 1
        l[493711] = 1
        l[494223] = 1
        l[494991] = 1
        l[495503] = 1
        l[495695] = 1
        l[496207] = 1
        l[496975] = 1
        l[497487] = 1
        l[497871] = 1
        l[498383] = 1
        l[499151] = 1
        l[499663] = 1
        l[499759] = 1
        l[500271] = 1
        l[501039] = 1
        l[501551] = 1
        l[501935] = 1
        l[502447] = 1
        l[503215] = 1
        l[503727] = 1
        l[503919] = 1
        l[504431] = 1
        l[505199] = 1
        l[505711] = 1
        l[506095] = 1
        l[506607] = 1
        l[507375] = 1
        l[507887] = 1
        l[507935] = 1
        l[508447] = 1
        l[509215] = 1
        l[509727] = 1
        l[510111] = 1
        l[510623] = 1
        l[511391] = 1
        l[511903] = 1
        l[512095] = 1
        l[512607] = 1
        l[513375] = 1
        l[513887] = 1
        l[514271] = 1
        l[514783] = 1
        l[515551] = 1
        l[516063] = 1
        l[516159] = 1
        l[516671] = 1
        l[517439] = 1
        l[517951] = 1
        l[518335] = 1
        l[518847] = 1
        l[519615] = 1
        l[520127] = 1
        l[520319] = 1
        l[520831] = 1
        l[521599] = 1
        l[522111] = 1
        l[522495] = 1
        l[523007] = 1
        l[523775] = 1
        l[524287] = 1
        l[524289] = 1
        l[525825] = 1
        l[526593] = 1
        l[528129] = 1
        l[528513] = 1
        l[530049] = 1
        l[530817] = 1
        l[532353] = 1
        l[532545] = 1
        l[534081] = 1
        l[534849] = 1
        l[536385] = 1
        l[536769] = 1
        l[538305] = 1
        l[539073] = 1
        l[540609] = 1
        l[540705] = 1
        l[542241] = 1
        l[543009] = 1
        l[544545] = 1
        l[544929] = 1
        l[546465] = 1
        l[547233] = 1
        l[548769] = 1
        l[548961] = 1
        l[550497] = 1
        l[551265] = 1
        l[552801] = 1
        l[553185] = 1
        l[554721] = 1
        l[555489] = 1
        l[557025] = 1
        l[557073] = 1
        l[558609] = 1
        l[559377] = 1
        l[560913] = 1
        l[561297] = 1
        l[562833] = 1
        l[563601] = 1
        l[565137] = 1
        l[565329] = 1
        l[566865] = 1
        l[567633] = 1
        l[569169] = 1
        l[569553] = 1
        l[571089] = 1
        l[571857] = 1
        l[573393] = 1
        l[573489] = 1
        l[575025] = 1
        l[575793] = 1
        l[577329] = 1
        l[577713] = 1
        l[579249] = 1
        l[580017] = 1
        l[581553] = 1
        l[581745] = 1
        l[583281] = 1
        l[584049] = 1
        l[585585] = 1
        l[585969] = 1
        l[587505] = 1
        l[588273] = 1
        l[589809] = 1
        l[589833] = 1
        l[591369] = 1
        l[592137] = 1
        l[593673] = 1
        l[594057] = 1
        l[595593] = 1
        l[596361] = 1
        l[597897] = 1
        l[598089] = 1
        l[599625] = 1
        l[600393] = 1
        l[601929] = 1
        l[602313] = 1
        l[603849] = 1
        l[604617] = 1
        l[606153] = 1
        l[606249] = 1
        l[607785] = 1
        l[608553] = 1
        l[610089] = 1
        l[610473] = 1
        l[612009] = 1
        l[612777] = 1
        l[614313] = 1
        l[614505] = 1
        l[616041] = 1
        l[616809] = 1
        l[618345] = 1
        l[618729] = 1
        l[620265] = 1
        l[621033] = 1
        l[622569] = 1
        l[622617] = 1
        l[624153] = 1
        l[624921] = 1
        l[626457] = 1
        l[626841] = 1
        l[628377] = 1
        l[629145] = 1
        l[630681] = 1
        l[630873] = 1
        l[632409] = 1
        l[633177] = 1
        l[634713] = 1
        l[635097] = 1
        l[636633] = 1
        l[637401] = 1
        l[638937] = 1
        l[639033] = 1
        l[640569] = 1
        l[641337] = 1
        l[642873] = 1
        l[643257] = 1
        l[644793] = 1
        l[645561] = 1
        l[647097] = 1
        l[647289] = 1
        l[648825] = 1
        l[649593] = 1
        l[651129] = 1
        l[651513] = 1
        l[653049] = 1
        l[653817] = 1
        l[655353] = 1
        l[655365] = 1
        l[656901] = 1
        l[657669] = 1
        l[659205] = 1
        l[659589] = 1
        l[661125] = 1
        l[661893] = 1
        l[663429] = 1
        l[663621] = 1
        l[665157] = 1
        l[665925] = 1
        l[667461] = 1
        l[667845] = 1
        l[669381] = 1
        l[670149] = 1
        l[671685] = 1
        l[671781] = 1
        l[673317] = 1
        l[674085] = 1
        l[675621] = 1
        l[676005] = 1
        l[677541] = 1
        l[678309] = 1
        l[679845] = 1
        l[680037] = 1
        l[681573] = 1
        l[682341] = 1
        l[683877] = 1
        l[684261] = 1
        l[685797] = 1
        l[686565] = 1
        l[688101] = 1
        l[688149] = 1
        l[689685] = 1
        l[690453] = 1
        l[691989] = 1
        l[692373] = 1
        l[693909] = 1
        l[694677] = 1
        l[696213] = 1
        l[696405] = 1
        l[697941] = 1
        l[698709] = 1
        l[700245] = 1
        l[700629] = 1
        l[702165] = 1
        l[702933] = 1
        l[704469] = 1
        l[704565] = 1
        l[706101] = 1
        l[706869] = 1
        l[708405] = 1
        l[708789] = 1
        l[710325] = 1
        l[711093] = 1
        l[712629] = 1
        l[712821] = 1
        l[714357] = 1
        l[715125] = 1
        l[716661] = 1
        l[717045] = 1
        l[718581] = 1
        l[719349] = 1
        l[720885] = 1
        l[720909] = 1
        l[722445] = 1
        l[723213] = 1
        l[724749] = 1
        l[725133] = 1
        l[726669] = 1
        l[727437] = 1
        l[728973] = 1
        l[729165] = 1
        l[730701] = 1
        l[731469] = 1
        l[733005] = 1
        l[733389] = 1
        l[734925] = 1
        l[735693] = 1
        l[737229] = 1
        l[737325] = 1
        l[738861] = 1
        l[739629] = 1
        l[741165] = 1
        l[741549] = 1
        l[743085] = 1
        l[743853] = 1
        l[745389] = 1
        l[745581] = 1
        l[747117] = 1
        l[747885] = 1
        l[749421] = 1
        l[749805] = 1
        l[751341] = 1
        l[752109] = 1
        l[753645] = 1
        l[753693] = 1
        l[755229] = 1
        l[755997] = 1
        l[757533] = 1
        l[757917] = 1
        l[759453] = 1
        l[760221] = 1
        l[761757] = 1
        l[761949] = 1
        l[763485] = 1
        l[764253] = 1
        l[765789] = 1
        l[766173] = 1
        l[767709] = 1
        l[768477] = 1
        l[770013] = 1
        l[770109] = 1
        l[771645] = 1
        l[772413] = 1
        l[773949] = 1
        l[774333] = 1
        l[775869] = 1
        l[776637] = 1
        l[778173] = 1
        l[778365] = 1
        l[779901] = 1
        l[780669] = 1
        l[782205] = 1
        l[782589] = 1
        l[784125] = 1
        l[784893] = 1
        l[786429] = 1
        l[786435] = 1
        l[787971] = 1
        l[788739] = 1
        l[790275] = 1
        l[790659] = 1
        l[792195] = 1
        l[792963] = 1
        l[794499] = 1
        l[794691] = 1
        l[796227] = 1
        l[796995] = 1
        l[798531] = 1
        l[798915] = 1
        l[800451] = 1
        l[801219] = 1
        l[802755] = 1
        l[802851] = 1
        l[804387] = 1
        l[805155] = 1
        l[806691] = 1
        l[807075] = 1
        l[808611] = 1
        l[809379] = 1
        l[810915] = 1
        l[811107] = 1
        l[812643] = 1
        l[813411] = 1
        l[814947] = 1
        l[815331] = 1
        l[816867] = 1
        l[817635] = 1
        l[819171] = 1
        l[819219] = 1
        l[820755] = 1
        l[821523] = 1
        l[823059] = 1
        l[823443] = 1
        l[824979] = 1
        l[825747] = 1
        l[827283] = 1
        l[827475] = 1
        l[829011] = 1
        l[829779] = 1
        l[831315] = 1
        l[831699] = 1
        l[833235] = 1
        l[834003] = 1
        l[835539] = 1
        l[835635] = 1
        l[837171] = 1
        l[837939] = 1
        l[839475] = 1
        l[839859] = 1
        l[841395] = 1
        l[842163] = 1
        l[843699] = 1
        l[843891] = 1
        l[845427] = 1
        l[846195] = 1
        l[847731] = 1
        l[848115] = 1
        l[849651] = 1
        l[850419] = 1
        l[851955] = 1
        l[851979] = 1
        l[853515] = 1
        l[854283] = 1
        l[855819] = 1
        l[856203] = 1
        l[857739] = 1
        l[858507] = 1
        l[860043] = 1
        l[860235] = 1
        l[861771] = 1
        l[862539] = 1
        l[864075] = 1
        l[864459] = 1
        l[865995] = 1
        l[866763] = 1
        l[868299] = 1
        l[868395] = 1
        l[869931] = 1
        l[870699] = 1
        l[872235] = 1
        l[872619] = 1
        l[874155] = 1
        l[874923] = 1
        l[876459] = 1
        l[876651] = 1
        l[878187] = 1
        l[878955] = 1
        l[880491] = 1
        l[880875] = 1
        l[882411] = 1
        l[883179] = 1
        l[884715] = 1
        l[884763] = 1
        l[886299] = 1
        l[887067] = 1
        l[888603] = 1
        l[888987] = 1
        l[890523] = 1
        l[891291] = 1
        l[892827] = 1
        l[893019] = 1
        l[894555] = 1
        l[895323] = 1
        l[896859] = 1
        l[897243] = 1
        l[898779] = 1
        l[899547] = 1
        l[901083] = 1
        l[901179] = 1
        l[902715] = 1
        l[903483] = 1
        l[905019] = 1
        l[905403] = 1
        l[906939] = 1
        l[907707] = 1
        l[909243] = 1
        l[909435] = 1
        l[910971] = 1
        l[911739] = 1
        l[913275] = 1
        l[913659] = 1
        l[915195] = 1
        l[915963] = 1
        l[917499] = 1
        l[917511] = 1
        l[919047] = 1
        l[919815] = 1
        l[921351] = 1
        l[921735] = 1
        l[923271] = 1
        l[924039] = 1
        l[925575] = 1
        l[925767] = 1
        l[927303] = 1
        l[928071] = 1
        l[929607] = 1
        l[929991] = 1
        l[931527] = 1
        l[932295] = 1
        l[933831] = 1
        l[933927] = 1
        l[935463] = 1
        l[936231] = 1
        l[937767] = 1
        l[938151] = 1
        l[939687] = 1
        l[940455] = 1
        l[941991] = 1
        l[942183] = 1
        l[943719] = 1
        l[944487] = 1
        l[946023] = 1
        l[946407] = 1
        l[947943] = 1
        l[948711] = 1
        l[950247] = 1
        l[950295] = 1
        l[951831] = 1
        l[952599] = 1
        l[954135] = 1
        l[954519] = 1
        l[956055] = 1
        l[956823] = 1
        l[958359] = 1
        l[958551] = 1
        l[960087] = 1
        l[960855] = 1
        l[962391] = 1
        l[962775] = 1
        l[964311] = 1
        l[965079] = 1
        l[966615] = 1
        l[966711] = 1
        l[968247] = 1
        l[969015] = 1
        l[970551] = 1
        l[970935] = 1
        l[972471] = 1
        l[973239] = 1
        l[974775] = 1
        l[974967] = 1
        l[976503] = 1
        l[977271] = 1
        l[978807] = 1
        l[979191] = 1
        l[980727] = 1
        l[981495] = 1
        l[983031] = 1
        l[983055] = 1
        l[984591] = 1
        l[985359] = 1
        l[986895] = 1
        l[987279] = 1
        l[988815] = 1
        l[989583] = 1
        l[991119] = 1
        l[991311] = 1
        l[992847] = 1
        l[993615] = 1
        l[995151] = 1
        l[995535] = 1
        l[997071] = 1
        l[997839] = 1
        l[999375] = 1
        l[999471] = 1
        l[1001007] = 1
        l[1001775] = 1
        l[1003311] = 1
        l[1003695] = 1
        l[1005231] = 1
        l[1005999] = 1
        l[1007535] = 1
        l[1007727] = 1
        l[1009263] = 1
        l[1010031] = 1
        l[1011567] = 1
        l[1011951] = 1
        l[1013487] = 1
        l[1014255] = 1
        l[1015791] = 1
        l[1015839] = 1
        l[1017375] = 1
        l[1018143] = 1
        l[1019679] = 1
        l[1020063] = 1
        l[1021599] = 1
        l[1022367] = 1
        l[1023903] = 1
        l[1024095] = 1
        l[1025631] = 1
        l[1026399] = 1
        l[1027935] = 1
        l[1028319] = 1
        l[1029855] = 1
        l[1030623] = 1
        l[1032159] = 1
        l[1032255] = 1
        l[1033791] = 1
        l[1034559] = 1
        l[1036095] = 1
        l[1036479] = 1
        l[1038015] = 1
        l[1038783] = 1
        l[1040319] = 1
        l[1040511] = 1
        l[1042047] = 1
        l[1042815] = 1
        l[1044351] = 1
        l[1044735] = 1
        l[1046271] = 1
        l[1047039] = 1
        l[1048575] = 1
        l[1048577] = 1
        l[1049601] = 1
        l[1051137] = 1
        l[1052161] = 1
        l[1052929] = 1
        l[1053953] = 1
        l[1055489] = 1
        l[1056513] = 1
        l[1056897] = 1
        l[1057921] = 1
        l[1059457] = 1
        l[1060481] = 1
        l[1061249] = 1
        l[1062273] = 1
        l[1063809] = 1
        l[1064833] = 1
        l[1065025] = 1
        l[1066049] = 1
        l[1067585] = 1
        l[1068609] = 1
        l[1069377] = 1
        l[1070401] = 1
        l[1071937] = 1
        l[1072961] = 1
        l[1073345] = 1
        l[1074369] = 1
        l[1075905] = 1
        l[1076929] = 1
        l[1077697] = 1
        l[1078721] = 1
        l[1080257] = 1
        l[1081281] = 1
        l[1081377] = 1
        l[1082401] = 1
        l[1083937] = 1
        l[1084961] = 1
        l[1085729] = 1
        l[1086753] = 1
        l[1088289] = 1
        l[1089313] = 1
        l[1089697] = 1
        l[1090721] = 1
        l[1092257] = 1
        l[1093281] = 1
        l[1094049] = 1
        l[1095073] = 1
        l[1096609] = 1
        l[1097633] = 1
        l[1097825] = 1
        l[1098849] = 1
        l[1100385] = 1
        l[1101409] = 1
        l[1102177] = 1
        l[1103201] = 1
        l[1104737] = 1
        l[1105761] = 1
        l[1106145] = 1
        l[1107169] = 1
        l[1108705] = 1
        l[1109729] = 1
        l[1110497] = 1
        l[1111521] = 1
        l[1113057] = 1
        l[1114081] = 1
        l[1114129] = 1
        l[1115153] = 1
        l[1116689] = 1
        l[1117713] = 1
        l[1118481] = 1
        l[1119505] = 1
        l[1121041] = 1
        l[1122065] = 1
        l[1122449] = 1
        l[1123473] = 1
        l[1125009] = 1
        l[1126033] = 1
        l[1126801] = 1
        l[1127825] = 1
        l[1129361] = 1
        l[1130385] = 1
        l[1130577] = 1
        l[1131601] = 1
        l[1133137] = 1
        l[1134161] = 1
        l[1134929] = 1
        l[1135953] = 1
        l[1137489] = 1
        l[1138513] = 1
        l[1138897] = 1
        l[1139921] = 1
        l[1141457] = 1
        l[1142481] = 1
        l[1143249] = 1
        l[1144273] = 1
        l[1145809] = 1
        l[1146833] = 1
        l[1146929] = 1
        l[1147953] = 1
        l[1149489] = 1
        l[1150513] = 1
        l[1151281] = 1
        l[1152305] = 1
        l[1153841] = 1
        l[1154865] = 1
        l[1155249] = 1
        l[1156273] = 1
        l[1157809] = 1
        l[1158833] = 1
        l[1159601] = 1
        l[1160625] = 1
        l[1162161] = 1
        l[1163185] = 1
        l[1163377] = 1
        l[1164401] = 1
        l[1165937] = 1
        l[1166961] = 1
        l[1167729] = 1
        l[1168753] = 1
        l[1170289] = 1
        l[1171313] = 1
        l[1171697] = 1
        l[1172721] = 1
        l[1174257] = 1
        l[1175281] = 1
        l[1176049] = 1
        l[1177073] = 1
        l[1178609] = 1
        l[1179633] = 1
        l[1179657] = 1
        l[1180681] = 1
        l[1182217] = 1
        l[1183241] = 1
        l[1184009] = 1
        l[1185033] = 1
        l[1186569] = 1
        l[1187593] = 1
        l[1187977] = 1
        l[1189001] = 1
        l[1190537] = 1
        l[1191561] = 1
        l[1192329] = 1
        l[1193353] = 1
        l[1194889] = 1
        l[1195913] = 1
        l[1196105] = 1
        l[1197129] = 1
        l[1198665] = 1
        l[1199689] = 1
        l[1200457] = 1
        l[1201481] = 1
        l[1203017] = 1
        l[1204041] = 1
        l[1204425] = 1
        l[1205449] = 1
        l[1206985] = 1
        l[1208009] = 1
        l[1208777] = 1
        l[1209801] = 1
        l[1211337] = 1
        l[1212361] = 1
        l[1212457] = 1
        l[1213481] = 1
        l[1215017] = 1
        l[1216041] = 1
        l[1216809] = 1
        l[1217833] = 1
        l[1219369] = 1
        l[1220393] = 1
        l[1220777] = 1
        l[1221801] = 1
        l[1223337] = 1
        l[1224361] = 1
        l[1225129] = 1
        l[1226153] = 1
        l[1227689] = 1
        l[1228713] = 1
        l[1228905] = 1
        l[1229929] = 1
        l[1231465] = 1
        l[1232489] = 1
        l[1233257] = 1
        l[1234281] = 1
        l[1235817] = 1
        l[1236841] = 1
        l[1237225] = 1
        l[1238249] = 1
        l[1239785] = 1
        l[1240809] = 1
        l[1241577] = 1
        l[1242601] = 1
        l[1244137] = 1
        l[1245161] = 1
        l[1245209] = 1
        l[1246233] = 1
        l[1247769] = 1
        l[1248793] = 1
        l[1249561] = 1
        l[1250585] = 1
        l[1252121] = 1
        l[1253145] = 1
        l[1253529] = 1
        l[1254553] = 1
        l[1256089] = 1
        l[1257113] = 1
        l[1257881] = 1
        l[1258905] = 1
        l[1260441] = 1
        l[1261465] = 1
        l[1261657] = 1
        l[1262681] = 1
        l[1264217] = 1
        l[1265241] = 1
        l[1266009] = 1
        l[1267033] = 1
        l[1268569] = 1
        l[1269593] = 1
        l[1269977] = 1
        l[1271001] = 1
        l[1272537] = 1
        l[1273561] = 1
        l[1274329] = 1
        l[1275353] = 1
        l[1276889] = 1
        l[1277913] = 1
        l[1278009] = 1
        l[1279033] = 1
        l[1280569] = 1
        l[1281593] = 1
        l[1282361] = 1
        l[1283385] = 1
        l[1284921] = 1
        l[1285945] = 1
        l[1286329] = 1
        l[1287353] = 1
        l[1288889] = 1
        l[1289913] = 1
        l[1290681] = 1
        l[1291705] = 1
        l[1293241] = 1
        l[1294265] = 1
        l[1294457] = 1
        l[1295481] = 1
        l[1297017] = 1
        l[1298041] = 1
        l[1298809] = 1
        l[1299833] = 1
        l[1301369] = 1
        l[1302393] = 1
        l[1302777] = 1
        l[1303801] = 1
        l[1305337] = 1
        l[1306361] = 1
        l[1307129] = 1
        l[1308153] = 1
        l[1309689] = 1
        l[1310713] = 1
        l[1310725] = 1
        l[1311749] = 1
        l[1313285] = 1
        l[1314309] = 1
        l[1315077] = 1
        l[1316101] = 1
        l[1317637] = 1
        l[1318661] = 1
        l[1319045] = 1
        l[1320069] = 1
        l[1321605] = 1
        l[1322629] = 1
        l[1323397] = 1
        l[1324421] = 1
        l[1325957] = 1
        l[1326981] = 1
        l[1327173] = 1
        l[1328197] = 1
        l[1329733] = 1
        l[1330757] = 1
        l[1331525] = 1
        l[1332549] = 1
        l[1334085] = 1
        l[1335109] = 1
        l[1335493] = 1
        l[1336517] = 1
        l[1338053] = 1
        l[1339077] = 1
        l[1339845] = 1
        l[1340869] = 1
        l[1342405] = 1
        l[1343429] = 1
        l[1343525] = 1
        l[1344549] = 1
        l[1346085] = 1
        l[1347109] = 1
        l[1347877] = 1
        l[1348901] = 1
        l[1350437] = 1
        l[1351461] = 1
        l[1351845] = 1
        l[1352869] = 1
        l[1354405] = 1
        l[1355429] = 1
        l[1356197] = 1
        l[1357221] = 1
        l[1358757] = 1
        l[1359781] = 1
        l[1359973] = 1
        l[1360997] = 1
        l[1362533] = 1
        l[1363557] = 1
        l[1364325] = 1
        l[1365349] = 1
        l[1366885] = 1
        l[1367909] = 1
        l[1368293] = 1
        l[1369317] = 1
        l[1370853] = 1
        l[1371877] = 1
        l[1372645] = 1
        l[1373669] = 1
        l[1375205] = 1
        l[1376229] = 1
        l[1376277] = 1
        l[1377301] = 1
        l[1378837] = 1
        l[1379861] = 1
        l[1380629] = 1
        l[1381653] = 1
        l[1383189] = 1
        l[1384213] = 1
        l[1384597] = 1
        l[1385621] = 1
        l[1387157] = 1
        l[1388181] = 1
        l[1388949] = 1
        l[1389973] = 1
        l[1391509] = 1
        l[1392533] = 1
        l[1392725] = 1
        l[1393749] = 1
        l[1395285] = 1
        l[1396309] = 1
        l[1397077] = 1
        l[1398101] = 1
        l[1399637] = 1
        l[1400661] = 1
        l[1401045] = 1
        l[1402069] = 1
        l[1403605] = 1
        l[1404629] = 1
        l[1405397] = 1
        l[1406421] = 1
        l[1407957] = 1
        l[1408981] = 1
        l[1409077] = 1
        l[1410101] = 1
        l[1411637] = 1
        l[1412661] = 1
        l[1413429] = 1
        l[1414453] = 1
        l[1415989] = 1
        l[1417013] = 1
        l[1417397] = 1
        l[1418421] = 1
        l[1419957] = 1
        l[1420981] = 1
        l[1421749] = 1
        l[1422773] = 1
        l[1424309] = 1
        l[1425333] = 1
        l[1425525] = 1
        l[1426549] = 1
        l[1428085] = 1
        l[1429109] = 1
        l[1429877] = 1
        l[1430901] = 1
        l[1432437] = 1
        l[1433461] = 1
        l[1433845] = 1
        l[1434869] = 1
        l[1436405] = 1
        l[1437429] = 1
        l[1438197] = 1
        l[1439221] = 1
        l[1440757] = 1
        l[1441781] = 1
        l[1441805] = 1
        l[1442829] = 1
        l[1444365] = 1
        l[1445389] = 1
        l[1446157] = 1
        l[1447181] = 1
        l[1448717] = 1
        l[1449741] = 1
        l[1450125] = 1
        l[1451149] = 1
        l[1452685] = 1
        l[1453709] = 1
        l[1454477] = 1
        l[1455501] = 1
        l[1457037] = 1
        l[1458061] = 1
        l[1458253] = 1
        l[1459277] = 1
        l[1460813] = 1
        l[1461837] = 1
        l[1462605] = 1
        l[1463629] = 1
        l[1465165] = 1
        l[1466189] = 1
        l[1466573] = 1
        l[1467597] = 1
        l[1469133] = 1
        l[1470157] = 1
        l[1470925] = 1
        l[1471949] = 1
        l[1473485] = 1
        l[1474509] = 1
        l[1474605] = 1
        l[1475629] = 1
        l[1477165] = 1
        l[1478189] = 1
        l[1478957] = 1
        l[1479981] = 1
        l[1481517] = 1
        l[1482541] = 1
        l[1482925] = 1
        l[1483949] = 1
        l[1485485] = 1
        l[1486509] = 1
        l[1487277] = 1
        l[1488301] = 1
        l[1489837] = 1
        l[1490861] = 1
        l[1491053] = 1
        l[1492077] = 1
        l[1493613] = 1
        l[1494637] = 1
        l[1495405] = 1
        l[1496429] = 1
        l[1497965] = 1
        l[1498989] = 1
        l[1499373] = 1
        l[1500397] = 1
        l[1501933] = 1
        l[1502957] = 1
        l[1503725] = 1
        l[1504749] = 1
        l[1506285] = 1
        l[1507309] = 1
        l[1507357] = 1
        l[1508381] = 1
        l[1509917] = 1
        l[1510941] = 1
        l[1511709] = 1
        l[1512733] = 1
        l[1514269] = 1
        l[1515293] = 1
        l[1515677] = 1
        l[1516701] = 1
        l[1518237] = 1
        l[1519261] = 1
        l[1520029] = 1
        l[1521053] = 1
        l[1522589] = 1
        l[1523613] = 1
        l[1523805] = 1
        l[1524829] = 1
        l[1526365] = 1
        l[1527389] = 1
        l[1528157] = 1
        l[1529181] = 1
        l[1530717] = 1
        l[1531741] = 1
        l[1532125] = 1
        l[1533149] = 1
        l[1534685] = 1
        l[1535709] = 1
        l[1536477] = 1
        l[1537501] = 1
        l[1539037] = 1
        l[1540061] = 1
        l[1540157] = 1
        l[1541181] = 1
        l[1542717] = 1
        l[1543741] = 1
        l[1544509] = 1
        l[1545533] = 1
        l[1547069] = 1
        l[1548093] = 1
        l[1548477] = 1
        l[1549501] = 1
        l[1551037] = 1
        l[1552061] = 1
        l[1552829] = 1
        l[1553853] = 1
        l[1555389] = 1
        l[1556413] = 1
        l[1556605] = 1
        l[1557629] = 1
        l[1559165] = 1
        l[1560189] = 1
        l[1560957] = 1
        l[1561981] = 1
        l[1563517] = 1
        l[1564541] = 1
        l[1564925] = 1
        l[1565949] = 1
        l[1567485] = 1
        l[1568509] = 1
        l[1569277] = 1
        l[1570301] = 1
        l[1571837] = 1
        l[1572861] = 1
        l[1572867] = 1
        l[1573891] = 1
        l[1575427] = 1
        l[1576451] = 1
        l[1577219] = 1
        l[1578243] = 1
        l[1579779] = 1
        l[1580803] = 1
        l[1581187] = 1
        l[1582211] = 1
        l[1583747] = 1
        l[1584771] = 1
        l[1585539] = 1
        l[1586563] = 1
        l[1588099] = 1
        l[1589123] = 1
        l[1589315] = 1
        l[1590339] = 1
        l[1591875] = 1
        l[1592899] = 1
        l[1593667] = 1
        l[1594691] = 1
        l[1596227] = 1
        l[1597251] = 1
        l[1597635] = 1
        l[1598659] = 1
        l[1600195] = 1
        l[1601219] = 1
        l[1601987] = 1
        l[1603011] = 1
        l[1604547] = 1
        l[1605571] = 1
        l[1605667] = 1
        l[1606691] = 1
        l[1608227] = 1
        l[1609251] = 1
        l[1610019] = 1
        l[1611043] = 1
        l[1612579] = 1
        l[1613603] = 1
        l[1613987] = 1
        l[1615011] = 1
        l[1616547] = 1
        l[1617571] = 1
        l[1618339] = 1
        l[1619363] = 1
        l[1620899] = 1
        l[1621923] = 1
        l[1622115] = 1
        l[1623139] = 1
        l[1624675] = 1
        l[1625699] = 1
        l[1626467] = 1
        l[1627491] = 1
        l[1629027] = 1
        l[1630051] = 1
        l[1630435] = 1
        l[1631459] = 1
        l[1632995] = 1
        l[1634019] = 1
        l[1634787] = 1
        l[1635811] = 1
        l[1637347] = 1
        l[1638371] = 1
        l[1638419] = 1
        l[1639443] = 1
        l[1640979] = 1
        l[1642003] = 1
        l[1642771] = 1
        l[1643795] = 1
        l[1645331] = 1
        l[1646355] = 1
        l[1646739] = 1
        l[1647763] = 1
        l[1649299] = 1
        l[1650323] = 1
        l[1651091] = 1
        l[1652115] = 1
        l[1653651] = 1
        l[1654675] = 1
        l[1654867] = 1
        l[1655891] = 1
        l[1657427] = 1
        l[1658451] = 1
        l[1659219] = 1
        l[1660243] = 1
        l[1661779] = 1
        l[1662803] = 1
        l[1663187] = 1
        l[1664211] = 1
        l[1665747] = 1
        l[1666771] = 1
        l[1667539] = 1
        l[1668563] = 1
        l[1670099] = 1
        l[1671123] = 1
        l[1671219] = 1
        l[1672243] = 1
        l[1673779] = 1
        l[1674803] = 1
        l[1675571] = 1
        l[1676595] = 1
        l[1678131] = 1
        l[1679155] = 1
        l[1679539] = 1
        l[1680563] = 1
        l[1682099] = 1
        l[1683123] = 1
        l[1683891] = 1
        l[1684915] = 1
        l[1686451] = 1
        l[1687475] = 1
        l[1687667] = 1
        l[1688691] = 1
        l[1690227] = 1
        l[1691251] = 1
        l[1692019] = 1
        l[1693043] = 1
        l[1694579] = 1
        l[1695603] = 1
        l[1695987] = 1
        l[1697011] = 1
        l[1698547] = 1
        l[1699571] = 1
        l[1700339] = 1
        l[1701363] = 1
        l[1702899] = 1
        l[1703923] = 1
        l[1703947] = 1
        l[1704971] = 1
        l[1706507] = 1
        l[1707531] = 1
        l[1708299] = 1
        l[1709323] = 1
        l[1710859] = 1
        l[1711883] = 1
        l[1712267] = 1
        l[1713291] = 1
        l[1714827] = 1
        l[1715851] = 1
        l[1716619] = 1
        l[1717643] = 1
        l[1719179] = 1
        l[1720203] = 1
        l[1720395] = 1
        l[1721419] = 1
        l[1722955] = 1
        l[1723979] = 1
        l[1724747] = 1
        l[1725771] = 1
        l[1727307] = 1
        l[1728331] = 1
        l[1728715] = 1
        l[1729739] = 1
        l[1731275] = 1
        l[1732299] = 1
        l[1733067] = 1
        l[1734091] = 1
        l[1735627] = 1
        l[1736651] = 1
        l[1736747] = 1
        l[1737771] = 1
        l[1739307] = 1
        l[1740331] = 1
        l[1741099] = 1
        l[1742123] = 1
        l[1743659] = 1
        l[1744683] = 1
        l[1745067] = 1
        l[1746091] = 1
        l[1747627] = 1
        l[1748651] = 1
        l[1749419] = 1
        l[1750443] = 1
        l[1751979] = 1
        l[1753003] = 1
        l[1753195] = 1
        l[1754219] = 1
        l[1755755] = 1
        l[1756779] = 1
        l[1757547] = 1
        l[1758571] = 1
        l[1760107] = 1
        l[1761131] = 1
        l[1761515] = 1
        l[1762539] = 1
        l[1764075] = 1
        l[1765099] = 1
        l[1765867] = 1
        l[1766891] = 1
        l[1768427] = 1
        l[1769451] = 1
        l[1769499] = 1
        l[1770523] = 1
        l[1772059] = 1
        l[1773083] = 1
        l[1773851] = 1
        l[1774875] = 1
        l[1776411] = 1
        l[1777435] = 1
        l[1777819] = 1
        l[1778843] = 1
        l[1780379] = 1
        l[1781403] = 1
        l[1782171] = 1
        l[1783195] = 1
        l[1784731] = 1
        l[1785755] = 1
        l[1785947] = 1
        l[1786971] = 1
        l[1788507] = 1
        l[1789531] = 1
        l[1790299] = 1
        l[1791323] = 1
        l[1792859] = 1
        l[1793883] = 1
        l[1794267] = 1
        l[1795291] = 1
        l[1796827] = 1
        l[1797851] = 1
        l[1798619] = 1
        l[1799643] = 1
        l[1801179] = 1
        l[1802203] = 1
        l[1802299] = 1
        l[1803323] = 1
        l[1804859] = 1
        l[1805883] = 1
        l[1806651] = 1
        l[1807675] = 1
        l[1809211] = 1
        l[1810235] = 1
        l[1810619] = 1
        l[1811643] = 1
        l[1813179] = 1
        l[1814203] = 1
        l[1814971] = 1
        l[1815995] = 1
        l[1817531] = 1
        l[1818555] = 1
        l[1818747] = 1
        l[1819771] = 1
        l[1821307] = 1
        l[1822331] = 1
        l[1823099] = 1
        l[1824123] = 1
        l[1825659] = 1
        l[1826683] = 1
        l[1827067] = 1
        l[1828091] = 1
        l[1829627] = 1
        l[1830651] = 1
        l[1831419] = 1
        l[1832443] = 1
        l[1833979] = 1
        l[1835003] = 1
        l[1835015] = 1
        l[1836039] = 1
        l[1837575] = 1
        l[1838599] = 1
        l[1839367] = 1
        l[1840391] = 1
        l[1841927] = 1
        l[1842951] = 1
        l[1843335] = 1
        l[1844359] = 1
        l[1845895] = 1
        l[1846919] = 1
        l[1847687] = 1
        l[1848711] = 1
        l[1850247] = 1
        l[1851271] = 1
        l[1851463] = 1
        l[1852487] = 1
        l[1854023] = 1
        l[1855047] = 1
        l[1855815] = 1
        l[1856839] = 1
        l[1858375] = 1
        l[1859399] = 1
        l[1859783] = 1
        l[1860807] = 1
        l[1862343] = 1
        l[1863367] = 1
        l[1864135] = 1
        l[1865159] = 1
        l[1866695] = 1
        l[1867719] = 1
        l[1867815] = 1
        l[1868839] = 1
        l[1870375] = 1
        l[1871399] = 1
        l[1872167] = 1
        l[1873191] = 1
        l[1874727] = 1
        l[1875751] = 1
        l[1876135] = 1
        l[1877159] = 1
        l[1878695] = 1
        l[1879719] = 1
        l[1880487] = 1
        l[1881511] = 1
        l[1883047] = 1
        l[1884071] = 1
        l[1884263] = 1
        l[1885287] = 1
        l[1886823] = 1
        l[1887847] = 1
        l[1888615] = 1
        l[1889639] = 1
        l[1891175] = 1
        l[1892199] = 1
        l[1892583] = 1
        l[1893607] = 1
        l[1895143] = 1
        l[1896167] = 1
        l[1896935] = 1
        l[1897959] = 1
        l[1899495] = 1
        l[1900519] = 1
        l[1900567] = 1
        l[1901591] = 1
        l[1903127] = 1
        l[1904151] = 1
        l[1904919] = 1
        l[1905943] = 1
        l[1907479] = 1
        l[1908503] = 1
        l[1908887] = 1
        l[1909911] = 1
        l[1911447] = 1
        l[1912471] = 1
        l[1913239] = 1
        l[1914263] = 1
        l[1915799] = 1
        l[1916823] = 1
        l[1917015] = 1
        l[1918039] = 1
        l[1919575] = 1
        l[1920599] = 1
        l[1921367] = 1
        l[1922391] = 1
        l[1923927] = 1
        l[1924951] = 1
        l[1925335] = 1
        l[1926359] = 1
        l[1927895] = 1
        l[1928919] = 1
        l[1929687] = 1
        l[1930711] = 1
        l[1932247] = 1
        l[1933271] = 1
        l[1933367] = 1
        l[1934391] = 1
        l[1935927] = 1
        l[1936951] = 1
        l[1937719] = 1
        l[1938743] = 1
        l[1940279] = 1
        l[1941303] = 1
        l[1941687] = 1
        l[1942711] = 1
        l[1944247] = 1
        l[1945271] = 1
        l[1946039] = 1
        l[1947063] = 1
        l[1948599] = 1
        l[1949623] = 1
        l[1949815] = 1
        l[1950839] = 1
        l[1952375] = 1
        l[1953399] = 1
        l[1954167] = 1
        l[1955191] = 1
        l[1956727] = 1
        l[1957751] = 1
        l[1958135] = 1
        l[1959159] = 1
        l[1960695] = 1
        l[1961719] = 1
        l[1962487] = 1
        l[1963511] = 1
        l[1965047] = 1
        l[1966071] = 1
        l[1966095] = 1
        l[1967119] = 1
        l[1968655] = 1
        l[1969679] = 1
        l[1970447] = 1
        l[1971471] = 1
        l[1973007] = 1
        l[1974031] = 1
        l[1974415] = 1
        l[1975439] = 1
        l[1976975] = 1
        l[1977999] = 1
        l[1978767] = 1
        l[1979791] = 1
        l[1981327] = 1
        l[1982351] = 1
        l[1982543] = 1
        l[1983567] = 1
        l[1985103] = 1
        l[1986127] = 1
        l[1986895] = 1
        l[1987919] = 1
        l[1989455] = 1
        l[1990479] = 1
        l[1990863] = 1
        l[1991887] = 1
        l[1993423] = 1
        l[1994447] = 1
        l[1995215] = 1
        l[1996239] = 1
        l[1997775] = 1
        l[1998799] = 1
        l[1998895] = 1
        l[1999919] = 1

        cnt = 0
        for i in range(a, b + 1):
            if l[i]:
                cnt += 1
        print(cnt)
    if (m == 3):
        cnt = 0
        for i in range(a, b + 1):
            if i == 0 or i == 1 or i == 6643:
                cnt += 1
            if i > 6644: break
        if b >= 1422773: cnt += 1
        print(cnt)
    elif m > 3:
        cnt = 0
        for i in range(a, b + 1):
            if i == 0 or i == 1:
                cnt += 1
            else:
                break
        print(cnt)


if __name__ == '__main__':
    main()