= {
8, 4096, 16, 512, 24, 4608, 32, 1024, 40, 5120, 48, 1536, 56, 5632, 64, 2048,
72, 6144, 80, 2560, 88, 6656, 96, 3072, 104, 7168, 112, 3584, 120, 7680, 128, 2048,
136, 4160, 144, 576, 152, 4672, 160, 1088, 168, 5184, 176, 1600, 184, 5696, 192, 2112,
200, 6208, 208, 2624, 216, 6720, 224, 3136, 232, 7232, 240, 3648, 248, 7744, 256, 2048,
264, 4224, 272, 640, 280, 4736, 288, 1152, 296, 5248, 304, 1664, 312, 5760, 320, 2176,
328, 6272, 336, 2688, 344, 6784, 352, 3200, 360, 7296, 368, 3712, 376, 7808, 384, 2112,
392, 4288, 400, 704, 408, 4800, 416, 1216, 424, 5312, 432, 1728, 440, 5824, 448, 2240,
456, 6336, 464, 2752, 472, 6848, 480, 3264, 488, 7360, 496, 3776, 504, 7872, 512, 2048,
520, 4352, 528, 768, 536, 4864, 544, 1280, 552, 5376, 560, 1792, 568, 5888, 576, 2304,
584, 6400, 592, 2816, 600, 6912, 608, 3328, 616, 7424, 624, 3840, 632, 7936, 640, 2176,
648, 4416, 656, 832, 664, 4928, 672, 1344, 680, 5440, 688, 1856, 696, 5952, 704, 2368,
712, 6464, 720, 2880, 728, 6976, 736, 3392, 744, 7488, 752, 3904, 760, 8000, 768, 2112,
776, 4480, 784, 896, 792, 4992, 800, 1408, 808, 5504, 816, 1920, 824, 6016, 832, 2432,
840, 6528, 848, 2944, 856, 7040, 864, 3456, 872, 7552, 880, 3968, 888, 8064, 896, 2240,
904, 4544, 912, 960, 920, 5056, 928, 1472, 936, 5568, 944, 1984, 952, 6080, 960, 2496,
968, 6592, 976, 3008, 984, 7104, 992, 3520, 1000, 7616, 1008, 4032, 1016, 8128, 1024, 4096,
1032, 4104, 1040, 4352, 1048, 4616, 1056, 4104, 1064, 5128, 1072, 1544, 1080, 5640, 1088, 2056,
1096, 6152, 1104, 2568, 1112, 6664, 1120, 3080, 1128, 7176, 1136, 3592, 1144, 7688, 1152, 6144,
1160, 4168, 1168, 6400, 1176, 4680, 1184, 6152, 1192, 5192, 1200, 1608, 1208, 5704, 1216, 2120,
1224, 6216, 1232, 2632, 1240, 6728, 1248, 3144, 1256, 7240, 1264, 3656, 1272, 7752, 1280, 4160,
1288, 4232, 1296, 4416, 1304, 4744, 1312, 4168, 1320, 5256, 1328, 1672, 1336, 5768, 1344, 2184,
1352, 6280, 1360, 2696, 1368, 6792, 1376, 3208, 1384, 7304, 1392, 3720, 1400, 7816, 1408, 6208,
1416, 4296, 1424, 6464, 1432, 4808, 1440, 6216, 1448, 5320, 1456, 1736, 1464, 5832, 1472, 2248,
1480, 6344, 1488, 2760, 1496, 6856, 1504, 3272, 1512, 7368, 1520, 3784, 1528, 7880, 1536, 4224,
1544, 4360, 1552, 4480, 1560, 4872, 1568, 4232, 1576, 5384, 1584, 1800, 1592, 5896, 1600, 2312,
1608, 6408, 1616, 2824, 1624, 6920, 1632, 3336, 1640, 7432, 1648, 3848, 1656, 7944, 1664, 6272,
1672, 4424, 1680, 6528, 1688, 4936, 1696, 6280, 1704, 5448, 1712, 1864, 1720, 5960, 1728, 2376,
1736, 6472, 1744, 2888, 1752, 6984, 1760, 3400, 1768, 7496, 1776, 3912, 1784, 8008, 1792, 4288,
1800, 4488, 1808, 4544, 1816, 5000, 1824, 4296, 1832, 5512, 1840, 1928, 1848, 6024, 1856, 2440,
1864, 6536, 1872, 2952, 1880, 7048, 1888, 3464, 1896, 7560, 1904, 3976, 1912, 8072, 1920, 6336,
1928, 4552, 1936, 6592, 1944, 5064, 1952, 6344, 1960, 5576, 1968, 1992, 1976, 6088, 1984, 2504,
1992, 6600, 2000, 3016, 2008, 7112, 2016, 3528, 2024, 7624, 2032, 4040, 2040, 8136, 2056, 4112,
2064, 2112, 2072, 4624, 2080, 4352, 2088, 5136, 2096, 4480, 2104, 5648, 2120, 6160, 2128, 2576,
2136, 6672, 2144, 3088, 2152, 7184, 2160, 3600, 2168, 7696, 2176, 2560, 2184, 4176, 2192, 2816,
2200, 4688, 2208, 2568, 2216, 5200, 2224, 2824, 2232, 5712, 2240, 2576, 2248, 6224, 2256, 2640,
2264, 6736, 2272, 3152, 2280, 7248, 2288, 3664, 2296, 7760, 2312, 4240, 2320, 2432, 2328, 4752,
2336, 6400, 2344, 5264, 2352, 6528, 2360, 5776, 2368, 2816, 2376, 6288, 2384, 2704, 2392, 6800,
2400, 3216, 2408, 7312, 2416, 3728, 2424, 7824, 2432, 2624, 2440, 4304, 2448, 2880, 2456, 4816,
2464, 2632, 2472, 5328, 2480, 2888, 2488, 5840, 2496, 2640, 2504, 6352, 2512, 2768, 2520, 6864,
2528, 3280, 2536, 7376, 2544, 3792, 2552, 7888, 2568, 4368, 2584, 4880, 2592, 4416, 2600, 5392,
2608, 4544, 2616, 5904, 2632, 6416, 2640, 2832, 2648, 6928, 2656, 3344, 2664, 7440, 2672, 3856,
2680, 7952, 2696, 4432, 2704, 2944, 2712, 4944, 2720, 4432, 2728, 5456, 2736, 2952, 2744, 5968,
2752, 2944, 2760, 6480, 2768, 2896, 2776, 6992, 2784, 3408, 2792, 7504, 2800, 3920, 2808, 8016,
2824, 4496, 2840, 5008, 2848, 6464, 2856, 5520, 2864, 6592, 2872, 6032, 2888, 6544, 2896, 2960,
2904, 7056, 2912, 3472, 2920, 7568, 2928, 3984, 2936, 8080, 2952, 4560, 2960, 3008, 2968, 5072,
2976, 6480, 2984, 5584, 2992, 3016, 3000, 6096, 3016, 6608, 3032, 7120, 3040, 3536, 3048, 7632,
3056, 4048, 3064, 8144, 3072, 4608, 3080, 4120, 3088, 4864, 3096, 4632, 3104, 4616, 3112, 5144,
3120, 4872, 3128, 5656, 3136, 4624, 3144, 6168, 3152, 4880, 3160, 6680, 3168, 4632, 3176, 7192,
3184, 3608, 3192, 7704, 3200, 6656, 3208, 4184, 3216, 6912, 3224, 4696, 3232, 6664, 3240, 5208,
3248, 6920, 3256, 5720, 3264, 6672, 3272, 6232, 3280, 6928, 3288, 6744, 3296, 6680, 3304, 7256,
3312, 3672, 3320, 7768, 3328, 4672, 3336, 4248, 3344, 4928, 3352, 4760, 3360, 4680, 3368, 5272,
3376, 4936, 3384, 5784, 3392, 4688, 3400, 6296, 3408, 4944, 3416, 6808, 3424, 4696, 3432, 7320,
3440, 3736, 3448, 7832, 3456, 6720, 3464, 4312, 3472, 6976, 3480, 4824, 3488, 6728, 3496, 5336,
3504, 6984, 3512, 5848, 3520, 6736, 3528, 6360, 3536, 6992, 3544, 6872, 3552, 6744, 3560, 7384,
3568, 3800, 3576, 7896, 3584, 4736, 3592, 4376, 3600, 4992, 3608, 4888, 3616, 4744, 3624, 5400,
3632, 5000, 3640, 5912, 3648, 4752, 3656, 6424, 3664, 5008, 3672, 6936, 3680, 4760, 3688, 7448,
3696, 3864, 3704, 7960, 3712, 6784, 3720, 4440, 3728, 7040, 3736, 4952, 3744, 6792, 3752, 5464,
3760, 7048, 3768, 5976, 3776, 6800, 3784, 6488, 3792, 7056, 3800, 7000, 3808, 6808, 3816, 7512,
3824, 3928, 3832, 8024, 3840, 4800, 3848, 4504, 3856, 5056, 3864, 5016, 3872, 4808, 3880, 5528,
3888, 5064, 3896, 6040, 3904, 4816, 3912, 6552, 3920, 5072, 3928, 7064, 3936, 4824, 3944, 7576,
3952, 3992, 3960, 8088, 3968, 6848, 3976, 4568, 3984, 7104, 3992, 5080, 4000, 6856, 4008, 5592,
4016, 7112, 4024, 6104, 4032, 6864, 4040, 6616, 4048, 7120, 4056, 7128, 4064, 6872, 4072, 7640,
4080, 7128, 4088, 8152, 4104, 4128, 4112, 4160, 4120, 4640, 4136, 5152, 4144, 4232, 4152, 5664,
4160, 4352, 4168, 6176, 4176, 4416, 4184, 6688, 4192, 4616, 4200, 7200, 4208, 4744, 4216, 7712,
4224, 4608, 4232, 4616, 4240, 4672, 4248, 4704, 4256, 4640, 4264, 5216, 4272, 4704, 4280, 5728,
4288, 4864, 4296, 6240, 4304, 4928, 4312, 6752, 4320, 4632, 4328, 7264, 4336, 4760, 4344, 7776,
4360, 4640, 4368, 4416, 4376, 4768, 4384, 6152, 4392, 5280, 4400, 6280, 4408, 5792, 4424, 6304,
4440, 6816, 4448, 6664, 4456, 7328, 4464, 6792, 4472, 7840, 4480, 4624, 4488, 4632, 4496, 4688,
4504, 4832, 4512, 6168, 4520, 5344, 4528, 6296, 4536, 5856, 4544, 4880, 4552, 6368, 4560, 4944,
4568, 6880, 4576, 6680, 4584, 7392, 4592, 6808, 4600, 7904, 4608, 6144, 4616, 6152, 4624, 6208,
4632, 4896, 4640, 6176, 4648, 5408, 4656, 6240, 4664, 5920, 4672, 6400, 4680, 6432, 4688, 6464,
4696, 6944, 4704, 6432, 4712, 7456, 4720, 4808, 4728, 7968, 4736, 6656, 4744, 6664, 4752, 6720,
4760, 4960, 4768, 6688, 4776, 5472, 4784, 6752, 4792, 5984, 4800, 6912, 4808, 6496, 4816, 6976,
4824, 7008, 4832, 6944, 4840, 7520, 4848, 7008, 4856, 8032, 4864, 6160, 4872, 6168, 4880, 6224,
4888, 5024, 4896, 6216, 4904, 5536, 4912, 6344, 4920, 6048, 4928, 6416, 4936, 6560, 4944, 6480,
4952, 7072, 4960, 6728, 4968, 7584, 4976, 6856, 4984, 8096, 4992, 6672, 5000, 6680, 5008, 6736,
5016, 5088, 5024, 6232, 5032, 5600, 5040, 6360, 5048, 6112, 5056, 6928, 5064, 6624, 5072, 6992,
5080, 7136, 5088, 6744, 5096, 7648, 5104, 6872, 5112, 8160, 5128, 5152, 5136, 5376, 5144, 5408,
5168, 5384, 5176, 5672, 5184, 5376, 5192, 6184, 5200, 5392, 5208, 6696, 5216, 5408, 5224, 7208,
5232, 5400, 5240, 7720, 5248, 7168, 5256, 7200, 5264, 7424, 5272, 7456, 5280, 7176, 5288, 7208,
5296, 7432, 5304, 5736, 5312, 7184, 5320, 6248, 5328, 7440, 5336, 6760, 5344, 7192, 5352, 7272,
5360, 7448, 5368, 7784, 5384, 5408, 5392, 5440, 5400, 5472, 5408, 6184, 5416, 7208, 5424, 5448,
5432, 5800, 5448, 6312, 5464, 6824, 5472, 6696, 5480, 7336, 5488, 6824, 5496, 7848, 5504, 7232,
5512, 7264, 5520, 7488, 5528, 7520, 5536, 7240, 5544, 7272, 5552, 7496, 5560, 5864, 5568, 7248,
5576, 6376, 5584, 7504, 5592, 6888, 5600, 7256, 5608, 7400, 5616, 7512, 5624, 7912, 5632, 7168,
5640, 7176, 5648, 7232, 5656, 7240, 5664, 7200, 5672, 7208, 5680, 7264, 5688, 5928, 5696, 7424,
5704, 6440, 5712, 7488, 5720, 6952, 5728, 7456, 5736, 7464, 5744, 7520, 5752, 7976, 5760, 7296,
5768, 7328, 5776, 7552, 5784, 7584, 5792, 7304, 5800, 7336, 5808, 7560, 5816, 5992, 5824, 7312,
5832, 6504, 5840, 7568, 5848, 7016, 5856, 7320, 5864, 7528, 5872, 7576, 5880, 8040, 5888, 7184,
5896, 7192, 5904, 7248, 5912, 7256, 5920, 6248, 5928, 7272, 5936, 6376, 5944, 6056, 5952, 7440,
5960, 6568, 5968, 7504, 5976, 7080, 5984, 6760, 5992, 7592, 6000, 6888, 6008, 8104, 6016, 7360,
6024, 7392, 6032, 7616, 6040, 7648, 6048, 7368, 6056, 7400, 6064, 7624, 6072, 6120, 6080, 7376,
6088, 6632, 6096, 7632, 6104, 7144, 6112, 7384, 6120, 7656, 6128, 7640, 6136, 8168, 6168, 6240,
6192, 6216, 6200, 7264, 6232, 6704, 6248, 7216, 6256, 6680, 6264, 7728, 6272, 6656, 6280, 6664,
6288, 6912, 6296, 6496, 6304, 6688, 6312, 6696, 6320, 6944, 6328, 7520, 6336, 6672, 6344, 6680,
6352, 6928, 6360, 6768, 6368, 6704, 6376, 7280, 6384, 6744, 6392, 7792, 6408, 6432, 6424, 6752,
6440, 7432, 6448, 6536, 6456, 7560, 6472, 6944, 6488, 6832, 6496, 6920, 6504, 7344, 6512, 7048,
6520, 7856, 6528, 6720, 6536, 6728, 6544, 6976, 6552, 7008, 6560, 6752, 6568, 7448, 6576, 7008,
6584, 7576, 6592, 6736, 6600, 6744, 6608, 6992, 6616, 6896, 6624, 6936, 6632, 7408, 6640, 7064,
6648, 7920, 6712, 7280, 6744, 6960, 6760, 7472, 6768, 6936, 6776, 7984, 6800, 6848, 6808, 6856,
6832, 6880, 6840, 6888, 6848, 7040, 6856, 7048, 6864, 7104, 6872, 7024, 6880, 7072, 6888, 7536,
6896, 7136, 6904, 8048, 6952, 7496, 6968, 7624, 6984, 7008, 7000, 7088, 7016, 7600, 7024, 7112,
7032, 8112, 7056, 7104, 7064, 7112, 7080, 7512, 7088, 7136, 7096, 7640, 7128, 7152, 7144, 7664,
7160, 8176, 7176, 7200, 7192, 7216, 7224, 7272, 7240, 7264, 7256, 7280, 7288, 7736, 7296, 7680,
7304, 7712, 7312, 7936, 7320, 7968, 7328, 7688, 7336, 7720, 7344, 7944, 7352, 7976, 7360, 7696,
7368, 7728, 7376, 7952, 7384, 7984, 7392, 7704, 7400, 7736, 7408, 7960, 7416, 7800, 7432, 7456,
7448, 7472, 7480, 7592, 7496, 7520, 7512, 7536, 7528, 7976, 7544, 7864, 7552, 7744, 7560, 7776,
7568, 8000, 7576, 8032, 7584, 7752, 7592, 7784, 7600, 8008, 7608, 8040, 7616, 7760, 7624, 7792,
7632, 8016, 7640, 8048, 7648, 7768, 7656, 7800, 7664, 8024, 7672, 7928, 7688, 7712, 7704, 7728,
7752, 7776, 7768, 7792, 7800, 7992, 7816, 7840, 7824, 8064, 7832, 8096, 7856, 8072, 7864, 8104,
7872, 8064, 7880, 8072, 7888, 8080, 7896, 8112, 7904, 8096, 7912, 8104, 7920, 8088, 7928, 8056,
7944, 7968, 7960, 7984, 8008, 8032, 8024, 8048, 8056, 8120, 8072, 8096, 8080, 8128, 8088, 8160,
8112, 8136, 8120, 8168, 8136, 8160, 8152, 8176
}
1.12.0