t = {4, 56, 76, 86, 134, 164, 182, 184, 206, 226, 232, 244, 274, 296, 344, 346, 394, 422, 434, 472, 496, 512, 560, 566, 574, 596, 602, 610, 622, 626, 644, 662, 664, 686, 692, 700, 722, 760, 764, 772, 790, 794, 800, 896, 904, 970, 980, 1004, 1022, 1060, 1066, 1072, 1084, 1094, 1096, 1136, 1142, 1154, 1186, 1226, 1274, 1306, 1312, 1316, 1354, 1366, 1372, 1390, 1402, 1406, 1420, 1456, 1466, 1472, 1480, 1484, 1516, 1544, 1550, 1570, 1586, 1600, 1604, 1610, 1612, 1630, 1646, 1696, 1724, 1730, 1744, 1772, 1834, 1862, 1876, 1880, 1886, 1924, 1934, 1940, 1942, 1960, 1970, 1976, 1990, 2026, 2030, 2054, 2104, 2120, 2144, 2152, 2170, 2174, 2194, 2204, 2212, 2246, 2254, 2276, 2290, 2300, 2344, 2374, 2386, 2390, 2396, 2404, 2426, 2444, 2446, 2452, 2456, 2510, 2534, 2536, 2576, 2620, 2632, 2642, 2650, 2692, 2696, 2732, 2746, 2782, 2800, 2864, 2866, 2876, 2906, 2912, 2950, 2954, 2962, 2972, 2984, 2990, 3004, 3010, 3104, 3130, 3140, 3166, 3200, 3202, 3226, 3280, 3290, 3292, 3296, 3304, 3310, 3320, 3326, 3340, 3392, 3394, 3406, 3412, 3422, 3440, 3472, 3496, 3524, 3530, 3544, 3560, 3562, 3574, 3592, 3602, 3614, 3622, 3640, 3670, 3676, 3686, 3716, 3734, 3794, 3824, 3856, 3860, 3866, 3874, 3892, 3902, 3934, 3952, 3956, 3962, 3964, 3980, 3994, 4040, 4060, 4076, 4094, 4096, 4112, 4154, 4160, 4190, 4222, 4232, 4264, 4270, 4276, 4280, 4306, 4354, 4360, 4370, 4382, 4406, 4424, 4426, 4456, 4462, 4474, 4480, 4484, 4502, 4504, 4540, 4544, 4550, 4564, 4582, 4586, 4592, 4594, 4606, 4622, 4672, 4696, 4712, 4714, 4724, 4732, 4736, 4750, 4766, 4784, 4792, 4810, 4822, 4844, 4864, 4882, 4886, 4900, 4904, 4924, 4942, 4952, 5000, 5002, 5006, 5026, 5050, 5084, 5086, 5090, 5110, 5156, 5182, 5186, 5194, 5200, 5210, 5224, 5252, 5314, 5330, 5354, 5356, 5384, 5386, 5432, 5452, 5462, 5480, 5494, 5506, 5510, 5540, 5546, 5552, 5572, 5594, 5596, 5602, 5614, 5624, 5660, 5672, 5726, 5734, 5750, 5770, 5776, 5792, 5840, 5870, 5926, 5932, 5936, 5944, 6016, 6026, 6040, 6062, 6070, 6076, 6082, 6100, 6142, 6146, 6164, 6206, 6212, 6220, 6302, 6310, 6316, 6320, 6322, 6362, 6394, 6404, 6436, 6454, 6484, 6500, 6520, 6524, 6554, 6566, 6584, 6602, 6632, 6646, 6670, 6674, 6680, 6736, 6740, 6806, 6826, 6832, 6836, 6850, 6854, 6862, 6866, 6880, 6890, 6932, 6940, 6944, 6950, 6982, 6986, 7010, 7030, 7046, 7052, 7066, 7070, 7090, 7132, 7154, 7160, 7186, 7210, 7214, 7244, 7262, 7336, 7360, 7366, 7384, 7394, 7396, 7402, 7420, 7496, 7532, 7556, 7570, 7580, 7610, 7694, 7696, 7714, 7724, 7742, 7762, 7792, 7802, 7814, 7840, 7912, 7916, 7982, 8000, 8036, 8042, 8054, 8072, 8114, 8150, 8164, 8210, 8224, 8236, 8260, 8270, 8282, 8312, 8332, 8350, 8374, 8380, 8390, 8396, 8422, 8450, 8452, 8462, 8494, 8504, 8506, 8516, 8540, 8542, 8546, 8590, 8596, 8614, 8686, 8716, 8722, 8726, 8750, 8780, 8794, 8812, 8816, 8824, 8830, 8834, 8854, 8870, 8872, 8882, 8890, 8900, 8912, 8924, 8926, 8980, 8984, 8996, 9004, 9026, 9040, 9062, 9074, 9116, 9134, 9176, 9184, 9206, 9220, 9232, 9242, 9244, 9290, 9292, 9296, 9344, 9370, 9376, 9380, 9410, 9422, 9424, 9440, 9442, 9470, 9530, 9550, 9596, 9626, 9634, 9640, 9682, 9706, 9736, 9800, 9802, 9872, 9892, 9914, 9916, 9926, 9940, 9946, 9974, 9976, 9982, 9992, 10016, 10034, 10060, 10066, 10082, 10096, 10112, 10124, 10126, 10144, 10154, 10156, 10180, 10184, 10222, 10244, 10264, 10286, 10294, 10322, 10352, 10354, 10360, 10364, 10376, 10390, 10394, 10444, 10454, 10462, 10480, 10490, 10496, 10514, 10522, 10562, 10576, 10580, 10606, 10654, 10690, 10706, 10720, 10726, 10756, 10804, 10816, 10822, 10856, 10886, 10892, 10894, 10910, 10930, 10940, 10952, 10996, 11012, 11060, 11090, 11092, 11116, 11120, 11122, 11144, 11146, 11162, 11180, 11182, 11210, 11222, 11224, 11246, 11270, 11272, 11276, 11294, 11300, 11320, 11342, 11354, 11372, 11416, 11456, 11480, 11494, 11512, 11536, 11542, 11624, 11630, 11636, 11642, 11650, 11666, 11690, 11720, 11732, 11740, 11752, 11756, 11780, 11794, 11854, 11860, 11864, 11882, 11906, 11920, 11966, 11984, 12040, 12044, 12046, 12064, 12074, 12092, 12130, 12140, 12194, 12202, 12212, 12214, 12226, 12230, 12244, 12250, 12256, 12302, 12352, 12362, 12392, 12422, 12442, 12454, 12460, 12484, 12490, 12506, 12590, 12604, 12616, 12634, 12670, 12674, 12700, 12706, 12734, 12796, 12800, 12806, 12824, 12832, 12844, 12854, 12874, 12880, 12890, 12910, 12916, 12940, 12952, 12956, 13006, 13012, 13036, 13042, 13054, 13066, 13084, 13096, 13150, 13160, 13190, 13216, 13250, 13252, 13262, 13280, 13292, 13322, 13330, 13336, 13346, 13366, 13372, 13384, 13406, 13436, 13456, 13460, 13484, 13492, 13502, 13510, 13520, 13526, 13546, 13576, 13630, 13642, 13652, 13670, 13694, 13714, 13726, 13742, 13744, 13766, 13780, 13784, 13786, 13790, 13870, 13912, 13936, 13946, 13972, 13994, 14006, 14020, 14090, 14116, 14122, 14132, 14134, 14176, 14210, 14252, 14260, 14272, 14284, 14312, 14350, 14372, 14384, 14420, 14422, 14464, 14482, 14486, 14492, 14510, 14512, 14546, 14566, 14594, 14606, 14612, 14624, 14662, 14714, 14716, 14744, 14746, 14774, 14800, 14804, 14840, 14876, 14890, 14900, 14914, 14930, 14956, 14962, 14980, 14990, 15040, 15044, 15046, 15052, 15056, 15064, 15080, 15086, 15100, 15122, 15176, 15184, 15190, 15214, 15220, 15236, 15254, 15260, 15274, 15280, 15296, 15326, 15352, 15364, 15374, 15386, 15392, 15404, 15410, 15442, 15446, 15452, 15460, 15476, 15484, 15506, 15550, 15556, 15592, 15614, 15626, 15646, 15680, 15710, 15724, 15740, 15760, 15766, 15782, 15806, 15820, 15824, 15850, 15880, 15940, 15982, 16036, 16040, 16072, 16094, 16102, 16106, 16124, 16160, 16172, 16174, 16216, 16234, 16250, 16262, 16264, 16282, 16306, 16310, 16330, 16340, 16342, 16360, 16366, 16394, 16430, 16436, 16442, 16492, 16502, 16510, 16516, 16520, 16582, 16600, 16642, 16682, 16696, 16702, 16724, 16750, 16790, 16814, 16850, 16856, 16876, 16894, 16900, 16906, 16946, 16970, 17032, 17062, 17080, 17096, 17192, 17194, 17264, 17282, 17290, 17294, 17324, 17326, 17342, 17356, 17384, 17420, 17426, 17440, 17444, 17464, 17492, 17564, 17566, 17570, 17602, 17606, 17614, 17626, 17630, 17654, 17660, 17674, 17684, 17690, 17696, 17704, 17720, 17746, 17804, 17812, 17824, 17852, 17870, 17900, 17906, 17920, 17972, 18052, 18112, 18130, 18152, 18202, 18230, 18236, 18250, 18280, 18286, 18290, 18320, 18334, 18340, 18344, 18356, 18382, 18424, 18460, 18470, 18472, 18476, 18526, 18532, 18542, 18556, 18574, 18580, 18584, 18592, 18616, 18650, 18652, 18676, 18682, 18706, 18712, 18724, 18782, 18790, 18824, 18844, 18866, 18896, 18902, 18932, 18934, 18944, 18952, 18956, 18974, 18980, 18992, 19000, 19046, 19100, 19112, 19114, 19144, 19160, 19172, 19174, 19214, 19222, 19256, 19270, 19280, 19292, 19322, 19324, 19370, 19372, 19406, 19442, 19450, 19456, 19460, 19466, 19504, 19510, 19526, 19564, 19582, 19616, 19622, 19634, 19636, 19642, 19660, 19666, 19670, 19676, 19684, 19714, 19732, 19760, 19774, 19786, 19790, 19792, 19802, 19820, 19862, 19874, 19882, 19900, 19904, 19916, 19940, 19942, 19982, 20006, 20014, 20062, 20080, 20096, 20104, 20110, 20126, 20132, 20140, 20180, 20192, 20204, 20206, 20212, 20234, 20272, 20290, 20296, 20330, 20362, 20386, 20392, 20404, 20474, 20506, 20512, 20516, 20542, 20572, 20584, 20612, 20626, 20630, 20642, 20644, 20654, 20656, 20696, 20710, 20714, 20720, 20756, 20764, 20776, 20782, 20800, 20840, 20860, 20866, 20870, 20890, 20924, 20930, 20960, 20972, 20990, 21002, 21016, 21062, 21064, 21074, 21094, 21122, 21140, 21146, 21170, 21206, 21242, 21310, 21322, 21370, 21382, 21412, 21430, 21442, 21470, 21482, 21496, 21512, 21536, 21554, 21580, 21584, 21592, 21596, 21616, 21644, 21652, 21686, 21700, 21716, 21724, 21772, 21800, 21806, 21826, 21830, 21832, 21842, 21850, 21892, 21902, 21982, 21986, 22012, 22052, 22054, 22072, 22082, 22094, 22106, 22112, 22120, 22126, 22150, 22180, 22184, 22190, 22196, 22232, 22240, 22262, 22292, 22294, 22310, 22324, 22364, 22420, 22430, 22436, 22456, 22472, 22480, 22490, 22504, 22516, 22522, 22546, 22570, 22574, 22604, 22624, 22690, 22702, 22714, 22736, 22742, 22754, 22760, 22802, 22810, 22822, 22856, 22862, 22864, 22886, 22892, 22936, 22964, 22982, 23026, 23050, 23054, 23066, 23080, 23092, 23114, 23134, 23150, 23164, 23174, 23192, 23194, 23212, 23216, 23234, 23264, 23272, 23284, 23296, 23302, 23306, 23312, 23326, 23332, 23356, 23360, 23362, 23366, 23374, 23404, 23432, 23440, 23444, 23446, 23450, 23470, 23482, 23512, 23564, 23582, 23590, 23594, 23620, 23636, 23684, 23690, 23692, 23704, 23720, 23722, 23746, 23750, 23764, 23776, 23816, 23830, 23842, 23900, 23920, 23932, 23944, 23950, 23972, 23986, 24010, 24032, 24052, 24110, 24152, 24170, 24182, 24196, 24214, 24220, 24272, 24284, 24290, 24380, 24416, 24422, 24430, 24476, 24482, 24490, 24494, 24496, 24542, 24550, 24562, 24590, 24622, 24632, 24634, 24686, 24724, 24760, 24776, 24784, 24790, 24830, 24872, 24880, 24914, 24920, 24944, 24962, 24980, 25004, 25012, 25042, 25046, 25052, 25064, 25070, 25082, 25120, 25180, 25186, 25192, 25196, 25202, 25214, 25220, 25252, 25280, 25312, 25334, 25340, 25342, 25360, 25384, 25396, 25400, 25460, 25472, 25480, 25490, 25516, 25526, 25574, 25612, 25634, 25654, 25706, 25742, 25756, 25774, 25780, 25826, 25834, 25862, 25880, 25900, 25904, 25906, 25910, 25934, 25946, 25964, 25966, 25972, 25984, 25990, 25994, 26014, 26030, 26054, 26060, 26062, 26090, 26116, 26132, 26200, 26210, 26240, 26242, 26252, 26272, 26284, 26300, 26314, 26330, 26372, 26390, 26396, 26410, 26414, 26434, 26440, 26494, 26536, 26560, 26602, 26614, 26660, 26684, 26702, 26704, 26716, 26756, 26762, 26764, 26770, 26782, 26800, 26842, 26866, 26870, 26876, 26882, 26896, 26954, 26966, 26980, 26992, 27014, 27034, 27044, 27052, 27092, 27112, 27152, 27154, 27230, 27286, 27380, 27406, 27446, 27454, 27484, 27490, 27496, 27512, 27526, 27562, 27572, 27584, 27590, 27596, 27604, 27626, 27644, 27646, 27650, 27664, 27674, 27682, 27692, 27706, 27722, 27740, 27766, 27770, 27776, 27794, 27806, 27814, 27836, 27854, 27952, 27980, 27992, 28000, 28042, 28046, 28070, 28090, 28112, 28114, 28120, 28144, 28162, 28172, 28216, 28246, 28252, 28274, 28276, 28280, 28286, 28294, 28360, 28396, 28400, 28420, 28442, 28450, 28472, 28484, 28504, 28510, 28522, 28532, 28562, 28564, 28574, 28576, 28612, 28636, 28652, 28664, 28690, 28702, 28744, 28756, 28762, 28780, 28784, 28786, 28790, 28814, 28826, 28844, 28912, 28916, 28954, 28982, 28990, 28994, 29014, 29032, 29066, 29086, 29122, 29140, 29156, 29164, 29170, 29186, 29210, 29252, 29264, 29284, 29302, 29332, 29360, 29366, 29386, 29390, 29404, 29470, 29474, 29476, 29492, 29500, 29504, 29516, 29522, 29536, 29560, 29576, 29596, 29624, 29626, 29632, 29644, 29674, 29690, 29704, 29710, 29726, 29752, 29764, 29780, 29782, 29816, 29842, 29864, 29884, 29890, 29906, 29914, 29924, 29926, 29984, 29992, 29996, 30004, 30010, 30032, 30050, 30086, 30134, 30136, 30160, 30190, 30194, 30256, 30302, 30344, 30386, 30410, 30454, 30466, 30500, 30506, 30542, 30550, 30556, 30584, 30586, 30592, 30640, 30682, 30692, 30760, 30766, 30772, 30796, 30802, 30842, 30860, 30880, 30890, 30902, 30914, 30934, 30944, 30946, 30964, 30982, 30992, 31000, 31024, 31034, 31070, 31102, 31136, 31150, 31184, 31210, 31214, 31216, 31220, 31226, 31234, 31256, 31282, 31292, 31294, 31304, 31334, 31354, 31364, 31366, 31370, 31390, 31412, 31424, 31472, 31510, 31516, 31574, 31576, 31580, 31594, 31640, 31646, 31684, 31700, 31726, 31754, 31796, 31804, 31826, 31852, 31874, 31906, 31916, 31936, 31954, 31982, 32000, 32074, 32104, 32140, 32144, 32162, 32176, 32180, 32194, 32200, 32204, 32206, 32224, 32234, 32242, 32260, 32284, 32312, 32320, 32342, 32386, 32404, 32426, 32434, 32456, 32462, 32476, 32486, 32510, 32546, 32612, 32650, 32662, 32684, 32710, 32732, 32794, 32804, 32806, 32816, 32822, 32852, 32872, 32924, 32936, 32960, 32966, 33002, 33020, 33026, 33034, 33046, 33050, 33064, 33074, 33100, 33112, 33134, 33170, 33212, 33214, 33280, 33284, 33292, 33314, 33340, 33362, 33364, 33382, 33386, 33392, 33400, 33404, 33424, 33434, 33460, 33466, 33470, 33580, 33590, 33620, 33622, 33646, 33652, 33656, 33664, 33706, 33736, 33776, 33784, 33800, 33806, 33820, 33832, 33842, 33854, 33862, 33922, 33950, 33974, 33994, 34024, 34040, 34066, 34076, 34112, 34114, 34124, 34126, 34156, 34162, 34192, 34196, 34202, 34216, 34220, 34246, 34250, 34310, 34352, 34384, 34400, 34406}