1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict

sums = defaultdict(list)
diffs = defaultdict(list)

res = {3: 2,6: 2,7: 3,9: 7,11: 5,12: 2,13: 3,14: 3,15: 8,17: 5,18: 7,19: 8,21: 17,22: 5,23: 9,24: 2,25: 6,26: 3,27: 21,28: 3,29: 9,30: 8,31: 12,33: 26,34: 5,35: 15,36: 7,37: 12,38: 8,39: 23,41: 14,42: 17,43: 17,44: 5,45: 31,46: 9,47: 18,48: 2,49: 24,50: 6,51: 32,52: 3,53: 18,54: 21,55: 23,56: 3,57: 41,58: 9,59: 23,60: 8,61: 21,62: 12,63: 58,65: 18,66: 26,67: 26,68: 5,69: 47,70: 15,71: 27,72: 7,73: 26,74: 12,75: 44,76: 8,77: 44,78: 23,79: 30,81: 62,82: 14,83: 32,84: 17,85: 26,86: 17,87: 53,88: 5,89: 32,90: 31,91: 42,92: 9,93: 62,94: 18,95: 38,96: 2,97: 35,98: 24,99: 86,100: 6,101: 36,102: 32,103: 39,104: 3,105: 83,106: 18,107: 41,108: 21,109: 39,110: 23,111: 68,112: 3,113: 41,114: 41,115: 45,116: 9,117: 82,118: 23,119: 56,120: 8,121: 55,122: 21,123: 77,124: 12,125: 42,126: 58,127: 48,129: 86,130: 18,131: 50,132: 26,133: 71,134: 26,135: 99,136: 5,137: 50,138: 47,139: 53,140: 15,141: 92,142: 27,143: 62,144: 7,145: 48,146: 26,147: 122,148: 12,149: 54,150: 44,151: 57,152: 8,153: 110,154: 44,155: 60,156: 23,157: 57,158: 30,159: 98,161: 84,162: 62,163: 62,164: 14,165: 122,166: 32,167: 63,168: 17,169: 60,170: 26,171: 137,172: 17,173: 63,174: 53,175: 81,176: 5,177: 116,178: 32,179: 68,180: 31,181: 66,182: 42,183: 113,184: 9,185: 63,186: 62,187: 83,188: 18,189: 180,190: 38,191: 72,192: 2,193: 71,194: 35,195: 116,196: 24,197: 72,198: 86,199: 75,200: 6,201: 131,202: 36,203: 96,204: 32,205: 71,206: 39,207: 160,208: 3,209: 104,210: 83,211: 80,212: 18,213: 137,214: 41,215: 83,216: 21,217: 111,218: 39,219: 137,220: 23,221: 77,222: 68,223: 84,224: 3,225: 157,226: 41,227: 86,228: 41,229: 84,230: 45,231: 221,232: 9,233: 86,234: 82,235: 90,236: 23,237: 152,238: 56,239: 90,240: 8,241: 89,242: 55,243: 184,244: 21,245: 120,246: 77,247: 101,248: 12,249: 161,250: 42,251: 95,252: 58,253: 122,254: 48,255: 155,257: 95,258: 86,259: 123,260: 18,261: 184,262: 50,263: 99,264: 26,265: 93,266: 71,267: 167,268: 26,269: 99,270: 99,271: 102,272: 5,273: 218,274: 50,275: 119,276: 47,277: 102,278: 53,279: 211,280: 15,281: 104,282: 92,283: 107,284: 27,285: 197,286: 62,287: 137,288: 7,289: 106,290: 48,291: 182,292: 26,293: 108,294: 122,295: 113,296: 12,297: 263,298: 54,299: 120,300: 44,301: 152,302: 57,303: 188,304: 8,305: 108,306: 110,307: 116,308: 44,309: 197,310: 60,311: 117,312: 23,313: 116,314: 57,315: 286,316: 30,317: 117,318: 98,319: 140,321: 206,322: 84,323: 134,324: 62,325: 111,326: 62,327: 203,328: 14,329: 165,330: 122,331: 125,332: 32,333: 235,334: 63,335: 128,336: 17,337: 125,338: 60,339: 212,340: 26,341: 161,342: 137,343: 171,344: 17,345: 233,346: 63,347: 131,348: 53,349: 129,350: 81,351: 258,352: 5,353: 131,354: 116,355: 135,356: 32,357: 287,358: 68,359: 135,360: 31,361: 151,362: 66,363: 275,364: 42,365: 131,366: 113,367: 138,368: 9,369: 263,370: 63,371: 177,372: 62,373: 138,374: 83,375: 230,376: 18,377: 135,378: 180,379: 143,380: 38,381: 242,382: 72,383: 144,384: 2,385: 218,386: 71,387: 290,388: 35,389: 144,390: 116,391: 158,392: 24,393: 251,394: 72,395: 150,396: 86,397: 147,398: 75,399: 356,400: 6,401: 149,402: 131,403: 159,404: 36,405: 302,406: 96,407: 179,408: 32,409: 152,410: 71,411: 257,412: 39,413: 206,414: 160,415: 158,416: 3,417: 266,418: 104,419: 158,420: 83,421: 156,422: 80,423: 313,424: 18,425: 149,426: 137,427: 204,428: 41,429: 317,430: 83,431: 162,432: 21,433: 161,434: 111,435: 266,436: 39,437: 197,438: 137,439: 165,440: 23,441: 415,442: 77,443: 167,444: 68,445: 161,446: 84,447: 278,448: 3,449: 167,450: 157,451: 200,452: 41,453: 287,454: 86,455: 213,456: 41,457: 170,458: 84,459: 341,460: 45,461: 171,462: 221,463: 174,464: 9,465: 308,466: 86,467: 176,468: 82,469: 233,470: 90,471: 293,472: 23,473: 221,474: 152,475: 194,476: 56,477: 337,478: 90,479: 180,480: 8,481: 174,482: 89,483: 422,484: 55,485: 176,486: 184,487: 183,488: 21,489: 311,490: 120,491: 185,492: 77,493: 179,494: 101,495: 416,496: 12,497: 246,498: 161,499: 188,500: 42,501: 317,502: 95,503: 189,504: 58,505: 183,506: 122,507: 314,508: 48,509: 189,510: 155,511: 245,513: 422,514: 95,515: 195,516: 86,517: 239,518: 123,519: 323,520: 18,521: 194,522: 184,523: 197,524: 50,525: 419,526: 99,527: 209,528: 26,529: 216,530: 93,531: 392,532: 71,533: 194,534: 167,535: 203,536: 26,537: 341,538: 99,539: 317,540: 99,541: 201,542: 102,543: 338,544: 5,545: 198,546: 218,547: 206,548: 50,549: 388,550: 119,551: 227,552: 47,553: 273,554: 102,555: 341,556: 53,557: 207,558: 211,559: 218,560: 15,561: 419,562: 104,563: 212,564: 92,565: 206,566: 107,567: 545,568: 27,569: 212,570: 197,571: 215,572: 62,573: 362,574: 137,575: 231,576: 7,577: 215,578: 106,579: 362,580: 48,581: 287,582: 182,583: 257,584: 26,585: 409,586: 108,587: 221,588: 122,589: 260,590: 113,591: 368,592: 12,593: 221,594: 263,595: 281,596: 54,597: 377,598: 120,599: 225,600: 44,601: 224,602: 152,603: 443,604: 57,605: 271,606: 188,607: 228,608: 8,609: 488,610: 108,611: 237,612: 110,613: 228,614: 116,615: 380,616: 44,617: 230,618: 197,619: 233,620: 60,621: 498,622: 117,623: 299,624: 23,625: 228,626: 116,627: 518,628: 57,629: 230,630: 286,631: 237,632: 30,633: 401,634: 117,635: 240,636: 98,637: 315,638: 140,639: 466,641: 239,642: 206,643: 242,644: 84,645: 422,646: 134,647: 243,648: 62,649: 299,650: 111,651: 557,652: 62,653: 243,654: 203,655: 248,656: 14,657: 467,658: 165,659: 248,660: 122,661: 246,662: 125,663: 410,664: 32,665: 353,666: 235,667: 270,668: 63,669: 422,670: 128,671: 296,672: 17,673: 251,674: 125,675: 495,676: 60,677: 252,678: 212,679: 326,680: 26,681: 431,682: 161,683: 257,684: 137,685: 251,686: 171,687: 428,688: 17,689: 252,690: 233,691: 260,692: 63,693: 749,694: 131,695: 263,696: 53,697: 257,698: 129,699: 437,700: 81,701: 261,702: 258,703: 290,704: 5,705: 458,706: 131,707: 339,708: 116,709: 264,710: 135,711: 517,712: 32,713: 309,714: 287,715: 311,716: 68,717: 452,718: 135,719: 270,720: 31,721: 354,722: 151,723: 452,724: 66,725: 261,726: 275,727: 273,728: 42,729: 549,730: 131,731: 287,732: 113,733: 273,734: 138,735: 608,736: 9,737: 338,738: 263,739: 278,740: 63,741: 512,742: 177,743: 279,744: 62,745: 273,746: 138,747: 545,748: 83,749: 368,750: 230,751: 282,752: 18,753: 476,754: 135,755: 285,756: 180,757: 282,758: 143,759: 611,760: 38,761: 284,762: 242,763: 366,764: 72,765: 539,766: 144,767: 296,768: 2,769: 287,770: 218,771: 482,772: 71,773: 288,774: 290,775: 306,776: 35,777: 623,778: 144,779: 323,780: 116,781: 356,782: 158,783: 576,784: 24,785: 288,786: 251,787: 296,788: 72,789: 497,790: 150,791: 380,792: 86,793: 291,794: 147,795: 491,796: 75,797: 297,798: 356,799: 311,800: 6,801: 569,802: 149,803: 356,804: 131,805: 420,806: 159,807: 503,808: 36,809: 302,810: 302,811: 305,812: 96,813: 512,814: 179,815: 308,816: 32,817: 356,818: 152,819: 745,820: 71,821: 306,822: 257,823: 309,824: 39,825: 608,826: 206,827: 311,828: 160,829: 309,830: 158,831: 518,832: 3,833: 413,834: 266,835: 315,836: 104,837: 657,838: 158,839: 315,840: 83,841: 312,842: 156,843: 527,844: 80,845: 306,846: 313,847: 490,848: 18,849: 536,850: 149,851: 345,852: 137,853: 318,854: 204,855: 671,856: 41,857: 320,858: 317,859: 323,860: 83,861: 692,862: 162,863: 324,864: 21,865: 318,866: 161,867: 542,868: 111,869: 395,870: 266,871: 335,872: 39,873: 620,874: 197,875: 417,876: 137,877: 327,878: 165,879: 548,880: 23,881: 329,882: 415,883: 332,884: 77,885: 572,886: 167,887: 333,888: 68,889: 435,890: 161,891: 791,892: 84,893: 386,894: 278,895: 338,896: 3,897: 608,898: 167,899: 357,900: 157,901: 332,902: 200,903: 761,904: 41,905: 333,906: 287,907: 341,908: 86,909: 643,910: 213,911: 342,912: 41,913: 416,914: 170,915: 566,916: 84,917: 449,918: 341,919: 345,920: 45,921: 581,922: 171,923: 354,924: 221,925: 336,926: 174,927: 670,928: 9,929: 347,930: 308,931: 512,932: 86,933: 587,934: 176,935: 410,936: 82,937: 350,938: 233,939: 587,940: 90,941: 351,942: 293,943: 383,944: 23,945: 894,946: 221,947: 356,948: 152,949: 350,950: 194,951: 593,952: 56,953: 356,954: 337,955: 360,956: 90,957: 707,958: 180,959: 461,960: 8,961: 384,962: 174,963: 698,964: 89,965: 356,966: 422,967: 363,968: 55,969: 674,970: 176,971: 365,972: 184,973: 476,974: 183,975: 599,976: 21,977: 365,978: 311,979: 434,980: 120,981: 694,982: 185,983: 369,984: 77,985: 363,986: 179,987: 827,988: 101,989: 422,990: 416,991: 372,992: 12,993: 626,994: 246,995: 375,996: 161,997: 372,998: 188,999: 735,1000: 42,1001: 569,1002: 317,1003: 389,1004: 95,1005: 647,1006: 189,1007: 416,1008: 58,1009: 377,1010: 183,1011: 632,1012: 122,1013: 378,1014: 314,1015: 483,1016: 48,1017: 722,1018: 189,1019: 383,1020: 155,1021: 381,1022: 245,1023: 806,1025: 374,1026: 422,1027: 393,1028: 95,1029: 857,1030: 195,1031: 387,1032: 86,1033: 386,1034: 239,1035: 796,1036: 123,1037: 383,1038: 323,1039: 390,1040: 18,1041: 656,1042: 194,1043: 501,1044: 184,1045: 512,1046: 197,1047: 653,1048: 50,1049: 392,1050: 419,1051: 395,1052: 99,1053: 785,1054: 209,1055: 398,1056: 26,1057: 516,1058: 216,1059: 662,1060: 93,1061: 396,1062: 392,1063: 399,1064: 71,1065: 683,1066: 194,1067: 473,1068: 167,1069: 399,1070: 203,1071: 977,1072: 26,1073: 396,1074: 341,1075: 419,1076: 99,1077: 677,1078: 317,1079: 413,1080: 99,1081: 459,1082: 201,1083: 755,1084: 102,1085: 555,1086: 338,1087: 408,1088: 5,1089: 930,1090: 198,1091: 410,1092: 218,1093: 408,1094: 206,1095: 680,1096: 50,1097: 410,1098: 388,1099: 528,1100: 119,1101: 692,1102: 227,1103: 414,1104: 47,1105: 395,1106: 273,1107: 818,1108: 102,1109: 414,1110: 341,1111: 491,1112: 53,1113: 893,1114: 207,1115: 420,1116: 211,1117: 417,1118: 218,1119: 698,1120: 15,1121: 482,1122: 419,1123: 422,1124: 104,1125: 793,1126: 212,1127: 609,1128: 92,1129: 422,1130: 206,1131: 701,1132: 107,1133: 512,1134: 545,1135: 428,1136: 27,1137: 716,1138: 212,1139: 440,1140: 197,1141: 557,1142: 215,1143: 823,1144: 62,1145: 423,1146: 362,1147: 456,1148: 137,1149: 722,1150: 231,1151: 432,1152: 7,1153: 431,1154: 215,1155: 1097,1156: 106,1157: 428,1158: 362,1159: 479,1160: 48,1161: 899,1162: 287,1163: 437,1164: 182,1165: 431,1166: 257,1167: 728,1168: 26,1169: 570,1170: 409,1171: 440,1172: 108,1173: 797,1174: 221,1175: 456,1176: 122,1177: 533,1178: 260,1179: 851,1180: 113,1181: 441,1182: 368,1183: 567,1184: 12,1185: 758,1186: 221,1187: 446,1188: 263,1189: 440,1190: 281,1191: 743,1192: 54,1193: 446,1194: 377,1195: 450,1196: 120,1197: 1208,1198: 225,1199: 530,1200: 44,1201: 449,1202: 224,1203: 752,1204: 152,1205: 446,1206: 443,1207: 464,1208: 57,1209: 803,1210: 271,1211: 582,1212: 188,1213: 453,1214: 228,1215: 910,1216: 8,1217: 455,1218: 488,1219: 495,1220: 108,1221: 902,1222: 237,1223: 459,1224: 110,1225: 606,1226: 228,1227: 767,1228: 116,1229: 459,1230: 380,1231: 462,1232: 44,1233: 875,1234: 230,1235: 506,1236: 197,1237: 462,1238: 233,1239: 1031,1240: 60,1241: 461,1242: 498,1243: 551,1244: 117,1245: 797,1246: 299,1247: 488,1248: 23,1249: 467,1250: 228,1251: 902,1252: 116,1253: 611,1254: 518,1255: 473,1256: 57,1257: 791,1258: 230,1259: 473,1260: 286,1261: 467,1262: 237,1263: 788,1264: 30,1265: 608,1266: 401,1267: 609,1268: 117,1269: 975,1270: 240,1271: 506,1272: 98,1273: 545,1274: 315,1275: 788,1276: 140,1277: 477,1278: 466,1279: 480,1281: 1028,1282: 239,1283: 482,1284: 206,1285: 476,1286: 242,1287: 1079,1288: 84,1289: 482,1290: 422,1291: 485,1292: 134,1293: 812,1294: 243,1295: 618,1296: 62,1297: 485,1298: 299,1299: 812,1300: 111,1301: 486,1302: 557,1303: 489,1304: 62,1305: 919,1306: 243,1307: 491,1308: 203,1309: 746,1310: 248,1311: 986,1312: 14,1313: 486,1314: 467,1315: 495,1316: 165,1317: 827,1318: 248,1319: 495,1320: 122,1321: 494,1322: 246,1323: 1293,1324: 125,1325: 486,1326: 410,1327: 498,1328: 32,1329: 836,1330: 353,1331: 600,1332: 235,1333: 557,1334: 270,1335: 830,1336: 63,1337: 651,1338: 422,1339: 510,1340: 128,1341: 949,1342: 296,1343: 515,1344: 17,1345: 498,1346: 251,1347: 842,1348: 125,1349: 575,1350: 495,1351: 650,1352: 60,1353: 1004,1354: 252,1355: 510,1356: 212,1357: 572,1358: 326,1359: 976,1360: 26,1361: 509,1362: 431,1363: 531,1364: 161,1365: 1091,1366: 257,1367: 513,1368: 137,1369: 510,1370: 251,1371: 857,1372: 171,1373: 513,1374: 428,1375: 605,1376: 17,1377: 1031,1378: 252,1379: 663,1380: 233,1381: 516,1382: 260,1383: 863,1384: 63,1385: 513,1386: 749,1387: 575,1388: 131,1389: 872,1390: 263,1391: 530,1392: 53,1393: 678,1394: 257,1395: 1051,1396: 129,1397: 629,1398: 437,1399: 525,1400: 81,1401: 881,1402: 261,1403: 570,1404: 258,1405: 521,1406: 290,1407: 1166,1408: 5,1409: 527,1410: 458,1411: 542,1412: 131,1413: 1000,1414: 339,1415: 533,1416: 116,1417: 525,1418: 264,1419: 1103,1420: 135,1421: 705,1422: 517,1423: 534,1424: 32,1425: 983,1426: 309,1427: 536,1428: 287,1429: 534,1430: 311,1431: 1053,1432: 68,1433: 536,1434: 452,1435: 686,1436: 135,1437: 902,1438: 270,1439: 540,1440: 31,1441: 650,1442: 354,1443: 896,1444: 151,1445: 532,1446: 452,1447: 543,1448: 66,1449: 1435,1450: 261,1451: 545,1452: 275,1453: 543,1454: 273,1455: 905,1456: 42,1457: 606,1458: 549,1459: 548,1460: 131,1461: 917,1462: 287,1463: 923,1464: 113,1465: 543,1466: 273,1467: 1055,1468: 138,1469: 545,1470: 608,1471: 552,1472: 9,1473: 926,1474: 338,1475: 569,1476: 263,1477: 719,1478: 278,1479: 920,1480: 63,1481: 554,1482: 512,1483: 557,1484: 177,1485: 1295,1486: 279,1487: 558,1488: 62,1489: 557,1490: 273,1491: 1232,1492: 138,1493: 558,1494: 545,1495: 603,1496: 83,1497: 941,1498: 368,1499: 563,1500: 230,1501: 638,1502: 282,1503: 1078,1504: 18,1505: 758,1506: 476,1507: 668,1508: 135,1509: 947,1510: 285,1511: 567,1512: 180,1513: 563,1514: 282,1515: 941,1516: 143,1517: 563,1518: 611,1519: 804,1520: 38,1521: 1075,1522: 284,1523: 572,1524: 242,1525: 561,1526: 366,1527: 953,1528: 72,1529: 689,1530: 539,1531: 575,1532: 144,1533: 1232,1534: 296,1535: 578,1536: 2,1537: 570,1538: 287,1539: 1274,1540: 218,1541: 647,1542: 482,1543: 579,1544: 71,1545: 983,1546: 288,1547: 740,1548: 290,1549: 579,1550: 306,1551: 1196,1552: 35,1553: 581,1554: 623,1555: 585,1556: 144,1557: 1102,1558: 323,1559: 585,1560: 116,1561: 759,1562: 356,1563: 977,1564: 158,1565: 581,1566: 576,1567: 588,1568: 24,1569: 986,1570: 288,1571: 590,1572: 251,1573: 706,1574: 296,1575: 1432,1576: 72,1577: 671,1578: 497,1579: 593,1580: 150,1581: 1052,1582: 380,1583: 594,1584: 86,1585: 588,1586: 291,1587: 1082,1588: 147,1589: 773,1590: 491,1591: 623,1592: 75,1593: 1217,1594: 297,1595: 701,1596: 356,1597: 597,1598: 311,1599: 995,1600: 6,1601: 599,1602: 569,1603: 771,1604: 149,1605: 1022,1606: 356,1607: 603,1608: 131,1609: 602,1610: 420,1611: 1157,1612: 159,1613: 603,1614: 503,1615: 665,1616: 36,1617: 1586,1618: 302,1619: 608,1620: 302,1621: 606,1622: 305,1623: 1013,1624: 96,1625: 594,1626: 512,1627: 611,1628: 179,1629: 1153,1630: 308,1631: 785,1632: 32,1633: 684,1634: 356,1635: 1016,1636: 152,1637: 612,1638: 745,1639: 725,1640: 71,1641: 1031,1642: 306,1643: 654,1644: 257,1645: 825,1646: 309,1647: 1212,1648: 39,1649: 614,1650: 608,1651: 627,1652: 206,1653: 1142,1654: 311,1655: 623,1656: 160,1657: 620,1658: 309,1659: 1367,1660: 158,1661: 746,1662: 518,1663: 624,1664: 3,1665: 1174,1666: 413,1667: 626,1668: 266,1669: 624,1670: 315,1671: 1043,1672: 104,1673: 813,1674: 657,1675: 644,1676: 158,1677: 1097,1678: 315,1679: 683,1680: 83,1681: 628,1682: 312,1683: 1418,1684: 156,1685: 626,1686: 527,1687: 812,1688: 80,1689: 1061,1690: 306,1691: 701,1692: 313,1693: 633,1694: 490,1695: 1055,1696: 18,1697: 635,1698: 536,1699: 638,1700: 149,1701: 1639,1702: 345,1703: 647,1704: 137,1705: 803,1706: 318,1707: 1067,1708: 204,1709: 639,1710: 671,1711: 662,1712: 41,1713: 1076,1714: 320,1715: 855,1716: 317,1717: 638,1718: 323,1719: 1231,1720: 83,1721: 644,1722: 692,1723: 647,1724: 162,1725: 1169,1726: 324,1727: 764,1728: 21,1729: 920,1730: 318,1731: 1082,1732: 161,1733: 648,1734: 542,1735: 653,1736: 111,1737: 1232,1738: 395,1739: 678,1740: 266,1741: 651,1742: 335,1743: 1436,1744: 39,1745: 648,1746: 620,1747: 656,1748: 197,1749: 1292,1750: 417,1751: 668,1752: 137,1753: 656,1754: 327,1755: 1287,1756: 165,1757: 854,1758: 548,1759: 660,1760: 23,1761: 1106,1762: 329,1763: 692,1764: 415,1765: 656,1766: 332,1767: 1301,1768: 77,1769: 657,1770: 572,1771: 1097,1772: 167,1773: 1255,1774: 333,1775: 681,1776: 68,1777: 665,1778: 435,1779: 1112,1780: 161,1781: 662,1782: 791,1783: 669,1784: 84,1785: 1430,1786: 386,1787: 671,1788: 278,1789: 669,1790: 338,1791: 1282,1792: 3,1793: 806,1794: 608,1795: 675,1796: 167,1797: 1127,1798: 357,1799: 866,1800: 157,1801: 674,1802: 332,1803: 1127,1804: 200,1805: 751,1806: 761,1807: 686,1808: 41,1809: 1376,1810: 333,1811: 680,1812: 287,1813: 900,1814: 341,1815: 1361,1816: 86,1817: 759,1818: 643,1819: 695,1820: 213,1821: 1142,1822: 342,1823: 684,1824: 41,1825: 674,1826: 416,1827: 1663,1828: 170,1829: 755,1830: 566,1831: 687,1832: 84,1833: 1193,1834: 449,1835: 690,1836: 341,1837: 824,1838: 345,1839: 1148,1840: 45,1841: 894,1842: 581,1843: 764,1844: 171,1845: 1304,1846: 354,1847: 693,1848: 221,1849: 727,1850: 336,1851: 1157,1852: 174,1853: 689,1854: 670,1855: 888,1856: 9,1857: 1166,1858: 347,1859: 821,1860: 308,1861: 696,1862: 512,1863: 1511,1864: 86,1865: 693,1866: 587,1867: 701,1868: 176,1869: 1502,1870: 410,1871: 702,1872: 82,1873: 701,1874: 350,1875: 1166,1876: 233,1877: 702,1878: 587,1879: 705,1880: 90,1881: 1751,1882: 351,1883: 906,1884: 293,1885: 687,1886: 383,1887: 1175,1888: 23,1889: 707,1890: 894,1891: 753,1892: 221,1893: 1187,1894: 356,1895: 713,1896: 152,1897: 921,1898: 350,1899: 1361,1900: 194,1901: 711,1902: 593,1903: 842,1904: 56,1905: 1208,1906: 356,1907: 716,1908: 337,1909: 797,1910: 360,1911: 1583,1912: 90,1913: 716,1914: 707,1915: 720,1916: 180,1917: 1452,1918: 461,1919: 794,1920: 8,1921: 716,1922: 384,1923: 1202,1924: 174,1925: 1094,1926: 698,1927: 752,1928: 89,1929: 1211,1930: 356,1931: 725,1932: 422,1933: 723,1934: 363,1935: 1436,1936: 55,1937: 720,1938: 674,1939: 933,1940: 176,1941: 1217,1942: 365,1943: 749,1944: 184,1945: 723,1946: 476,1947: 1493,1948: 183,1949: 729,1950: 599,1951: 732,1952: 21,1953: 1894,1954: 365,1955: 791,1956: 311,1957: 827,1958: 434,1959: 1223,1960: 120,1961: 729,1962: 694,1963: 744,1964: 185,1965: 1247,1966: 369,1967: 947,1968: 77,1969: 884,1970: 363,1971: 1454,1972: 179,1973: 738,1974: 827,1975: 756,1976: 101,1977: 1241,1978: 422,1979: 743,1980: 416,1981: 962,1982: 372,1983: 1238,1984: 12,1985: 738,1986: 626,1987: 746,1988: 246,1989: 1406,1990: 375,1991: 881,1992: 161,1993: 746,1994: 372,1995: 1772,1996: 188,1997: 747,1998: 735,1999: 750,2000: 42,2001: 1358,2002: 569,2003: 752,2004: 317,2005: 746,2006: 389,2007: 1435,2008: 95,2009: 998,2010: 647,2011: 755,2012: 189,2013: 1487,2014: 416,2015: 798,2016: 58,2017: 755,2018: 377,2019: 1262,2020: 183,2021: 827,2022: 632,2023: 973,2024: 122,2025: 1508,2026: 378,2027: 761,2028: 314,2029: 759,2030: 483,2031: 1268,2032: 48,2033: 860,2034: 722,2035: 896,2036: 189,2037: 1637,2038: 383,2039: 765,2040: 155,2041: 759,2042: 381,2043: 1463,2044: 245,2045: 761,2046: 806,2047: 833,2049: 1286,2050: 374,2051: 987,2052: 422,2053: 768,2054: 393,2055: 1280,2056: 95,2057: 926,2058: 857,2059: 792,2060: 195,2061: 1459,2062: 387,2063: 774,2064: 86,2065: 1028,2066: 386,2067: 1286,2068: 239,2069: 774,2070: 796,2071: 857,2072: 123,2073: 1301,2074: 383,2075: 794,2076: 323,2077: 854,2078: 390,2079: 2330,2080: 18,2081: 779,2082: 656,2083: 782,2084: 194,2085: 1322,2086: 501,2087: 783,2088: 184,2089: 782,2090: 512,2091: 1307,2092: 197,2093: 1095,2094: 653,2095: 788,2096: 50,2097: 1487,2098: 392,2099: 788,2100: 419,2101: 941,2102: 395,2103: 1313,2104: 99,2105: 783,2106: 785,2107: 1097,2108: 209,2109: 1457,2110: 398,2111: 792,2112: 26,2113: 791,2114: 516,2115: 1561,2116: 216,2117: 788,2118: 662,2119: 803,2120: 93,2121: 1703,2122: 396,2123: 941,2124: 392,2125: 782,2126: 399,2127: 1328,2128: 71,2129: 797,2130: 683,2131: 800,2132: 194,2133: 1611,2134: 473,2135: 1023,2136: 167,2137: 800,2138: 399,2139: 1547,2140: 203,2141: 801,2142: 977,2143: 804,2144: 26,2145: 1580,2146: 396,2147: 890,2148: 341,2149: 1043,2150: 419,2151: 1537,2152: 99,2153: 806,2154: 677,2155: 810,2156: 317,2157: 1352,2158: 413,2159: 821,2160: 99,2161: 809,2162: 459,2163: 1772,2164: 201,2165: 806,2166: 755,2167: 959,2168: 102,2169: 1538,2170: 555,2171: 822,2172: 338,2173: 809,2174: 408,2175: 1349,2176: 5,2177: 1056,2178: 930,2179: 818,2180: 198,2181: 1367,2182: 410,2183: 845,2184: 218,2185: 983,2186: 408,2187: 1643,2188: 206,2189: 980,2190: 680,2191: 1055,2192: 50,2193: 1439,2194: 410,2195: 825,2196: 388,2197: 819,2198: 528,2199: 1373,2200: 119,2201: 903,2202: 692,2203: 827,2204: 227,2205: 2071,2206: 414,2207: 828,2208: 47,2209: 864,2210: 395,2211: 1688,2212: 273,2213: 828,2214: 818,2215: 833,2216: 102,2217: 1391,2218: 414,2219: 1068,2220: 341,2221: 831,2222: 491,2223: 1742,2224: 53,2225: 824,2226: 893,2227: 848,2228: 207,2229: 1397,2230: 420,2231: 908,2232: 211,2233: 1271,2234: 417,2235: 1391,2236: 218,2237: 837,2238: 698,2239: 840,2240: 15,2241: 1694,2242: 482,2243: 842,2244: 419,2245: 836,2246: 422,2247: 1841,2248: 104,2249: 837,2250: 793,2251: 845,2252: 212,2253: 1412,2254: 609,2255: 995,2256: 92,2257: 840,2258: 422,2259: 1616,2260: 206,2261: 1205,2262: 701,2263: 902,2264: 107,2265: 1433,2266: 512,2267: 851,2268: 545,2269: 849,2270: 428,2271: 1418,2272: 27,2273: 851,2274: 716,2275: 1086,2276: 212,2277: 2075,2278: 440,2279: 893,2280: 197,2281: 854,2282: 557,2283: 1427,2284: 215,2285: 851,2286: 823,2287: 858,2288: 62,2289: 1838,2290: 423,2291: 879,2292: 362,2293: 858,2294: 456,2295: 1688,2296: 137,2297: 860,2298: 722,2299: 1145,2300: 231,2301: 1487,2302: 432,2303: 1194,2304: 7,2305: 858,2306: 431,2307: 1442,2308: 215,2309: 864,2310: 1097,2311: 867,2312: 106,2313: 1640,2314: 428,2315: 870,2316: 362,2317: 1124,2318: 479,2319: 1448,2320: 48,2321: 1040,2322: 899,2323: 945,2324: 287,2325: 1544,2326: 437,2327: 881,2328: 182,2329: 869,2330: 431,2331: 2122,2332: 257,2333: 873,2334: 728,2335: 878,2336: 26,2337: 1619,2338: 570,2339: 878,2340: 409,2341: 876,2342: 440,2343: 1781,2344: 108,2345: 1163,2346: 797,2347: 881,2348: 221,2349: 1751,2350: 456,2351: 882,2352: 122,2353: 876,2354: 533,2355: 1466,2356: 260,2357: 882,2358: 851,2359: 1136,2360: 113,2361: 1481,2362: 441,2363: 899,2364: 368,2365: 1097,2366: 567,2367: 1690,2368: 12,2369: 984,2370: 758,2371: 890,2372: 221,2373: 1907,2374: 446,2375: 980,2376: 263,2377: 890,2378: 440,2379: 1481,2380: 281,2381: 891,2382: 743,2383: 894,2384: 54,2385: 1684,2386: 446,2387: 1448,2388: 377,2389: 894,2390: 450,2391: 1493,2392: 120,2393: 896,2394: 1208,2395: 900,2396: 225,2397: 1562,2398: 530,2399: 900,2400: 44,2401: 1200,2402: 449,2403: 1772,2404: 224,2405: 882,2406: 752,2407: 923,2408: 152,2409: 1784,2410: 446,2411: 905,2412: 443,2413: 1016,2414: 464,2415: 2108,2416: 57,2417: 905,2418: 803,2419: 938,2420: 271,2421: 1714,2422: 582,2423: 909,2424: 188,2425: 899,2426: 453,2427: 1517,2428: 228,2429: 1178,2430: 910,2431: 1073,2432: 8,2433: 1526,2434: 455,2435: 915,2436: 488,2437: 912,2438: 495,2439: 1741,2440: 108,2441: 914,2442: 902,2443: 1176,2444: 237,2445: 1547,2446: 459,2447: 918,2448: 110,2449: 1002,2450: 606,2451: 1778,2452: 228,2453: 1097,2454: 767,2455: 923,2456: 116,2457: 2325,2458: 459,2459: 923,2460: 380,2461: 1022,2462: 462,2463: 1538,2464: 44,2465: 905,2466: 875,2467: 926,2468: 230,2469: 1547,2470: 506,2471: 1190,2472: 197,2473: 926,2474: 462,2475: 2072,2476: 233,2477: 927,2478: 1031,2479: 956,2480: 60,2481: 1556,2482: 461,2483: 939,2484: 498,2485: 1230,2486: 551,2487: 1553,2488: 117,2489: 1049,2490: 797,2491: 972,2492: 299,2493: 1765,2494: 488,2495: 938,2496: 23,2497: 1118,2498: 467,2499: 2072,2500: 228,2501: 932,2502: 902,2503: 939,2504: 116,2505: 1583,2506: 611,2507: 1020,2508: 518,2509: 935,2510: 473,2511: 1994,2512: 57,2513: 1218,2514: 791,2515: 945,2516: 230,2517: 1577,2518: 473,2519: 1115,2520: 286,2521: 944,2522: 467,2523: 1574,2524: 237,2525: 936,2526: 788,2527: 1354,2528: 30,2529: 1793,2530: 608,2531: 950,2532: 401,2533: 944,2534: 609,2535: 1574,2536: 117,2537: 1031,2538: 975,2539: 953,2540: 240,2541: 2450,2542: 506,2543: 954,2544: 98,2545: 948,2546: 545,2547: 1820,2548: 315,2549: 954,2550: 788,2551: 957,2552: 140,2553: 1733,2554: 477,2555: 1226,2556: 466,2557: 957,2558: 480,2559: 1598,2561: 954,2562: 1028,2563: 1136,2564: 239,2565: 2090,2566: 482,2567: 974,2568: 206,2569: 1245,2570: 476,2571: 1607,2572: 242,2573: 1052,2574: 1079,2575: 981,2576: 84,2577: 1616,2578: 482,2579: 968,2580: 422,2581: 962,2582: 485,2583: 2354,2584: 134,2585: 1193,2586: 812,2587: 978,2588: 243,2589: 1622,2590: 618,2591: 972,2592: 62,2593: 971,2594: 485,2595: 1616,2596: 299,2597: 1290,2598: 812,2599: 1058,2600: 111,2601: 1845,2602: 486,2603: 1079,2604: 557,2605: 971,2606: 489,2607: 1976,2608: 62,2609: 977,2610: 919,2611: 1257,2612: 243,2613: 1682,2614: 491,2615: 983,2616: 203,2617: 980,2618: 746,2619: 1931,2620: 248,2621: 981,2622: 986,2623: 1028,2624: 14,2625: 2105,2626: 486,2627: 1011,2628: 467,2629: 1175,2630: 495,2631: 1643,2632: 165,2633: 986,2634: 827,2635: 1046,2636: 248,2637: 1867,2638: 495,2639: 1266,2640: 122,2641: 1112,2642: 494,2643: 1652,2644: 246,2645: 1080,2646: 1293,2647: 993,2648: 125,2649: 1661,2650: 486,2651: 1175,2652: 410,2653: 1286,2654: 498,2655: 1946,2656: 32,2657: 995,2658: 836,2659: 998,2660: 353,2661: 1667,2662: 600,2663: 999,2664: 235,2665: 980,2666: 557,2667: 2177,2668: 270,2669: 995,2670: 830,2671: 1002,2672: 63,2673: 2372,2674: 651,2675: 1019,2676: 422,2677: 1002,2678: 510,2679: 1931,2680: 128,2681: 1299,2682: 949,2683: 1007,2684: 296,2685: 1697,2686: 515,2687: 1008,2688: 17,2689: 1007,2690: 498,2691: 2071,2692: 251,2693: 1008,2694: 842,2695: 1583,2696: 125,2697: 1793,2698: 575,2699: 1013,2700: 495,2701: 1007,2702: 650,2703: 1685,2704: 60,2705: 1008,2706: 1004,2707: 1016,2708: 252,2709: 2585,2710: 510,2711: 1017,2712: 212,2713: 1016,2714: 572,2715: 1691,2716: 326,2717: 1331,2718: 976,2719: 1020,2720: 26,2721: 1706,2722: 509,2723: 1311,2724: 431,2725: 1011,2726: 531,2727: 2007,2728: 161,2729: 1022,2730: 1091,2731: 1025,2732: 257,2733: 1712,2734: 513,2735: 1028,2736: 137,2737: 1433,2738: 510,2739: 2078,2740: 251,2741: 1026,2742: 857,2743: 1037,2744: 171,2745: 1939,2746: 513,2747: 1061,2748: 428,2749: 1029,2750: 605,2751: 2246,2752: 17,2753: 1031,2754: 1031,2755: 1136,2756: 252,2757: 1727,2758: 663,2759: 1100,2760: 233,2761: 1235,2762: 516,2763: 1973,2764: 260,2765: 1365,2766: 863,2767: 1038,2768: 63,2769: 1778,2770: 513,2771: 1052,2772: 749,2773: 1121,2774: 575,2775: 1724,2776: 131,2777: 1040,2778: 872,2779: 1338,2780: 263,2781: 2088,2782: 530,2783: 1360,2784: 53,2785: 1038,2786: 678,2787: 1742,2788: 257,2789: 1044,2790: 1051,2791: 1047,2792: 129,2793: 2561,2794: 629,2795: 1091,2796: 437,2797: 1047,2798: 525,2799: 1996,2800: 81,2801: 1049,2802: 881,2803: 1052,2804: 261,2805: 2072,2806: 570,2807: 1352,2808: 258,2809: 1050,2810: 521,2811: 1757,2812: 290,2813: 1049,2814: 1166,2815: 1058,2816: 5,2817: 1997,2818: 527,2819: 1058,2820: 458,2821: 1446,2822: 542,2823: 1763,2824: 131,2825: 1049,2826: 1000,2827: 1253,2828: 339,2829: 1922,2830: 533,2831: 1172,2832: 116,2833: 1061,2834: 525,2835: 2717,2836: 264,2837: 1062,2838: 1103,2839: 1076,2840: 135,2841: 1781,2842: 705,2843: 1067,2844: 517,2845: 1061,2846: 534,2847: 1775,2848: 32,2849: 1622,2850: 983,2851: 1070,2852: 309,2853: 2020,2854: 536,2855: 1073,2856: 287,2857: 1070,2858: 534,2859: 1787,2860: 311,2861: 1071,2862: 1053,2863: 1379,2864: 68,2865: 1808,2866: 536,2867: 1119,2868: 452,2869: 1205,2870: 686,2871: 2405,2872: 135,2873: 1067,2874: 902,2875: 1167,2876: 270,2877: 2312,2878: 540,2879: 1080,2880: 31,2881: 1166,2882: 650,2883: 1922,2884: 354,2885: 1076,2886: 896,2887: 1083,2888: 151,2889: 2171,2890: 532,2891: 1487,2892: 452,2893: 1292,2894: 543,2895: 1805,2896: 66,2897: 1085,2898: 1435,2899: 1095,2900: 261,2901: 1817,2902: 545,2903: 1089,2904: 275,2905: 1433,2906: 543,2907: 2285,2908: 273,2909: 1089,2910: 905,2911: 1121,2912: 42,2913: 1826,2914: 606,2915: 1286,2916: 549,2917: 1092,2918: 548,2919: 2381,2920: 131,2921: 1209,2922: 917,2923: 1122,2924: 287,2925: 2062,2926: 923,2927: 1098,2928: 113,2929: 1092,2930: 543,2931: 1832,2932: 273,2933: 1421,2934: 1055,2935: 1103,2936: 138,2937: 2174,2938: 545,2939: 1103,2940: 608,2941: 1097,2942: 552,2943: 2166,2944: 9,2945: 1298,2946: 926,2947: 1419,2948: 338,2949: 1847,2950: 569,2951: 1115,2952: 263,2953: 1106,2954: 719,2955: 1841,2956: 278,2957: 1107,2958: 920,2959: 1310,2960: 63,2961: 2812,2962: 554,2963: 1112,2964: 512,2965: 1106,2966: 557,2967: 2111,2968: 177,2969: 1112,2970: 1295,2971: 1115,2972: 279,2973: 1862,2974: 558,2975: 1424,2976: 62,2977: 1110,2978: 557,2979: 2126,2980: 273,2981: 1331,2982: 1232,2983: 1235,2984: 138,2985: 1883,2986: 558,2987: 1140,2988: 545,2989: 1485,2990: 603,2991: 1868,2992: 83,2993: 1118,2994: 941,2995: 1125,2996: 368,2997: 2234,2998: 563,2999: 1125,3000: 230,3001: 1124,3002: 638,3003: 2852,3004: 282,3005: 1121,3006: 1078,3007: 1199,3008: 18,3009: 1949,3010: 758,3011: 1130,3012: 476,3013: 1247,3014: 668,3015: 2201,3016: 135,3017: 1461,3018: 947,3019: 1133,3020: 285,3021: 2087,3022: 567,3023: 1134,3024: 180,3025: 1357,3026: 563,3027: 1892,3028: 282,3029: 1130,3030: 941,3031: 1460,3032: 143,3033: 2150,3034: 563,3035: 1140,3036: 611,3037: 1137,3038: 804,3039: 1898,3040: 38,3041: 1139,3042: 1075,3043: 1154,3044: 284,3045: 2441,3046: 572,3047: 1349,3048: 242,3049: 1142,3050: 561,3051: 2249,3052: 366,3053: 1232,3054: 953,3055: 1188,3056: 72,3057: 1916,3058: 689,3059: 1772,3060: 539,3061: 1146,3062: 575,3063: 1913,3064: 144,3065: 1143,3066: 1232,3067: 1151,3068: 296,3069: 2738,3070: 578,3071: 1178,3072: 2,3073: 1488,3074: 570,3075: 1913,3076: 287,3077: 1148,3078: 1274,3079: 1155,3080: 218,3081: 1973,3082: 647,3083: 1157,3084: 482,3085: 1151,3086: 579,3087: 2914,3088: 71,3089: 1157,3090: 983,3091: 1370,3092: 288,3093: 1937,3094: 740,3095: 1163,3096: 290,3097: 1301,3098: 579,3099: 1937,3100: 306,3101: 1502,3102: 1196,3103: 1184,3104: 35,3105: 2484,3106: 581,3107: 1173,3108: 623,3109: 1164,3110: 585,3111: 1940,3112: 144,3113: 1391,3114: 1102,3115: 1496,3116: 323,3117: 1952,3118: 585,3119: 1170,3120: 116,3121: 1169,3122: 759,3123: 2228,3124: 356,3125: 1164,3126: 977,3127: 1211,3128: 158,3129: 2513,3130: 581,3131: 1248,3132: 576,3133: 1169,3134: 588,3135: 2564,3136: 24,3137: 1175,3138: 986,3139: 1232,3140: 288,3141: 2224,3142: 590,3143: 1514,3144: 251,3145: 1160,3146: 706,3147: 1967,3148: 296,3149: 1268,3150: 1432,3151: 1283,3152: 72,3153: 1976,3154: 671,3155: 1185,3156: 497,3157: 1799,3158: 593,3159: 2365,3160: 150,3161: 1179,3162: 1052,3163: 1187,3164: 380,3165: 1997,3166: 594,3167: 1188,3168: 86,3169: 1187,3170: 588,3171: 2582,3172: 291,3173: 1331,3174: 1082,3175: 1206,3176: 147,3177: 2252,3178: 773,3179: 1409,3180: 491,3181: 1191,3182: 623,3183: 1988,3184: 75,3185: 1578,3186: 1217,3187: 1196,3188: 297,3189: 1997,3190: 701,3191: 1197,3192: 356,3193: 1299,3194: 597,3195: 2326,3196: 311,3197: 1322,3198: 995,3199: 1541,3200: 6,3201: 2369,3202: 599,3203: 1202,3204: 569,3205: 1196,3206: 771,3207: 2003,3208: 149,3209: 1202,3210: 1022,3211: 1328,3212: 356,3213: 3044,3214: 603,3215: 1208,3216: 131,3217: 1205,3218: 602,3219: 2006,3220: 420,3221: 1206,3222: 1157,3223: 1427,3224: 159,3225: 2108,3226: 603,3227: 1554,3228: 503,3229: 1209,3230: 665,3231: 2302,3232: 36,3233: 1206,3234: 1586,3235: 1215,3236: 302,3237: 2072,3238: 608,3239: 1244,3240: 302,3241: 1569,3242: 606,3243: 2297,3244: 305,3245: 1487,3246: 1013,3247: 1229,3248: 96,3249: 2562,3250: 594,3251: 1220,3252: 512,3253: 1218,3254: 611,3255: 2783,3256: 179,3257: 1220,3258: 1153,3259: 1223,3260: 308,3261: 2042,3262: 785,3263: 1232,3264: 32,3265: 1218,3266: 684,3267: 2890,3268: 356,3269: 1583,3270: 1016,3271: 1227,3272: 152,3273: 2051,3274: 612,3275: 1244,3276: 745,3277: 1223,3278: 725,3279: 2048,3280: 71,3281: 1226,3282: 1031,3283: 1682,3284: 306,3285: 2324,3286: 654,3287: 1361,3288: 257,3289: 1583,3290: 825,3291: 2057,3292: 309,3293: 1229,3294: 1212,3295: 1238,3296: 39,3297: 2648,3298: 614,3299: 1238,3300: 608,3301: 1236,3302: 627,3303: 2353,3304: 206,3305: 1233,3306: 1142,3307: 1241,3308: 311,3309: 2072,3310: 623,3311: 1976,3312: 160,3313: 1241,3314: 620,3315: 2054,3316: 309,3317: 1349,3318: 1367,3319: 1245,3320: 158,3321: 2480,3322: 746,3323: 1247,3324: 518,3325: 1769,3326: 624,3327: 2078,3328: 3,3329: 1247,3330: 1174,3331: 1250,3332: 413,3333: 2462,3334: 626,3335: 1353,3336: 266,3337: 1341,3338: 624,3339: 3040,3340: 315,3341: 1247,3342: 1043,3343: 1254,3344: 104,3345: 2108,3346: 813,3347: 1256,3348: 657,3349: 1250,3350: 644,3351: 2093,3352: 158,3353: 1623,3354: 1097,3355: 1481,3356: 315,3357: 2377,3358: 683,3359: 1260,3360: 83,3361: 1259,3362: 628,3363: 2408,3364: 312,3365: 1256,3366: 1418,3367: 1617,3368: 156,3369: 2111,3370: 626,3371: 1265,3372: 527,3373: 1263,3374: 812,3375: 2481,3376: 80,3377: 1508,3378: 1061,3379: 1347,3380: 306,3381: 3047,3382: 701,3383: 1280,3384: 313,3385: 1263,3386: 633,3387: 2117,3388: 490,3389: 1269,3390: 1055,3391: 1272,3392: 18,3393: 2398,3394: 635,3395: 1631,3396: 536,3397: 1367,3398: 638,3399: 2561,3400: 149,3401: 1427,3402: 1639,3403: 1307,3404: 345,3405: 2147,3406: 647,3407: 1278,3408: 137,3409: 1650,3410: 803,3411: 2432,3412: 318,3413: 1278,3414: 1067,3415: 1283,3416: 204,3417: 2204,3418: 639,3419: 1290,3420: 671,3421: 1526,3422: 662,3423: 2786,3424: 41,3425: 1274,3426: 1076,3427: 1395,3428: 320,3429: 2565,3430: 855,3431: 1340,3432: 317,3433: 1286,3434: 638,3435: 2141,3436: 323,3437: 1664,3438: 1231,3439: 1424,3440: 83,3441: 2288,3442: 644,3443: 1526,3444: 692,3445: 1272,3446: 647,3447: 2455,3448: 162,3449: 1292,3450: 1169,3451: 1658,3452: 324,3453: 2162,3454: 764,3455: 1298,3456: 21,3457: 1295,3458: 920,3459: 2162,3460: 318,3461: 1296,3462: 1082,3463: 1299,3464: 161,3465: 3731,3466: 648,3467: 1301,3468: 542,3469: 1299,3470: 653,3471: 2165,3472: 111,3473: 1434,3474: 1232,3475: 1319,3476: 395,3477: 2402,3478: 678,3479: 1779,3480: 266,3481: 1351,3482: 651,3483: 2723,3484: 335,3485: 1289,3486: 1436,3487: 1544,3488: 39,3489: 2186,3490: 648,3491: 1310,3492: 620,3493: 1691,3494: 656,3495: 2180,3496: 197,3497: 1305,3498: 1292,3499: 1313,3500: 417,3501: 2479,3502: 668,3503: 1397,3504: 137,3505: 1308,3506: 656,3507: 2852,3508: 327,3509: 1576,3510: 1287,3511: 1317,3512: 165,3513: 2201,3514: 854,3515: 1451,3516: 548,3517: 1317,3518: 660,3519: 2711,3520: 23,3521: 1704,3522: 1106,3523: 1329,3524: 329,3525: 2294,3526: 692,3527: 1323,3528: 415,3529: 1322,3530: 656,3531: 2663,3532: 332,3533: 1323,3534: 1301,3535: 1698,3536: 77,3537: 2648,3538: 657,3539: 1328,3540: 572,3541: 1326,3542: 1097,3543: 2213,3544: 167,3545: 1323,3546: 1255,3547: 1331,3548: 333,3549: 2849,3550: 681,3551: 1370,3552: 68,3553: 1745,3554: 665,3555: 2581,3556: 435,3557: 1332,3558: 1112,3559: 1335,3560: 161,3561: 2231,3562: 662,3563: 1716,3564: 791,3565: 1545,3566: 669,3567: 2225,3568: 84,3569: 1436,3570: 1430,3571: 1340,3572: 386,3573: 2530,3574: 671,3575: 1574,3576: 278,3577: 1778,3578: 669,3579: 2237,3580: 338,3581: 1341,3582: 1282,3583: 1344,3584: 3,3585: 2258,3586: 806,3587: 1358,3588: 608,3589: 1340,3590: 675,3591: 3761,3592: 167,3593: 1346,3594: 1127,3595: 1350,3596: 357,3597: 2657,3598: 866,3599: 1394,3600: 157,3601: 1344,3602: 674,3603: 2252,3604: 332,3605: 1770,3606: 1127,3607: 1353,3608: 200,3609: 2558,3610: 751,3611: 1470,3612: 761,3613: 1353,3614: 686,3615: 2255,3616: 41,3617: 1355,3618: 1376,3619: 2150,3620: 333,3621: 2327,3622: 680,3623: 1359,3624: 287,3625: 1344,3626: 900,3627: 2734,3628: 341,3629: 1520,3630: 1361,3631: 1362,3632: 86,3633: 2918,3634: 759,3635: 1365,3636: 643,3637: 1362,3638: 695,3639: 2273,3640: 213,3641: 1625,3642: 1142,3643: 1367,3644: 342,3645: 2733,3646: 684,3647: 1757,3648: 41,3649: 1364,3650: 674,3651: 2282,3652: 416,3653: 1364,3654: 1663,3655: 1430,3656: 170,3657: 2483,3658: 755,3659: 1373,3660: 566,3661: 1772,3662: 687,3663: 3068,3664: 84,3665: 1368,3666: 1193,3667: 1520,3668: 449,3669: 2297,3670: 690,3671: 1377,3672: 341,3673: 1376,3674: 824,3675: 3044,3676: 345,3677: 1377,3678: 1148,3679: 1388,3680: 45,3681: 2609,3682: 894,3683: 1401,3684: 581,3685: 1682,3686: 764,3687: 2303,3688: 171,3689: 1892,3690: 1304,3691: 1385,3692: 354,3693: 2312,3694: 693,3695: 1388,3696: 221,3697: 1385,3698: 727,3699: 2726,3700: 336,3701: 1386,3702: 1157,3703: 1947,3704: 174,3705: 2555,3706: 689,3707: 1643,3708: 670,3709: 1389,3710: 888,3711: 2318,3712: 9,3713: 1488,3714: 1166,3715: 1395,3716: 347,3717: 3503,3718: 821,3719: 1395,3720: 308,3721: 1392,3722: 696,3723: 2327,3724: 512,3725: 1386,3726: 1511,3727: 1398,3728: 86,3729: 2759,3730: 693,3731: 1793,3732: 587,3733: 1398,3734: 701,3735: 2711,3736: 176,3737: 1395,3738: 1502,3739: 1403,3740: 410,3741: 2447,3742: 702,3743: 1550,3744: 82,3745: 1838,3746: 701,3747: 2342,3748: 350,3749: 1547,3750: 1166,3751: 1795,3752: 233,3753: 2807,3754: 702,3755: 1410,3756: 587,3757: 1399,3758: 705,3759: 3056,3760: 90,3761: 1409,3762: 1751,3763: 1449,3764: 351,3765: 2372,3766: 906,3767: 1413,3768: 293,3769: 1412,3770: 687,3771: 2687,3772: 383,3773: 2228,3774: 1175,3775: 1431,3776: 23,3777: 2366,3778: 707,3779: 1418,3780: 894,3781: 1583,3782: 753,3783: 2360,3784: 221,3785: 1413,3786: 1187,3787: 1824,3788: 356,3789: 2683,3790: 713,3791: 1433,3792: 152,3793: 1421,3794: 921,3795: 3047,3796: 350,3797: 1422,3798: 1361,3799: 1445,3800: 194,3801: 3053,3802: 711,3803: 1427,3804: 593,3805: 1421,3806: 842,3807: 2960,3808: 56,3809: 1422,3810: 1208,3811: 1455,3812: 356,3813: 2537,3814: 716,3815: 1833,3816: 337,3817: 1703,3818: 797,3819: 2723,3820: 360,3821: 1431,3822: 1583,3823: 1434,3824: 90,3825: 2702,3826: 716,3827: 1502,3828: 707,3829: 1853,3830: 720,3831: 2393,3832: 180,3833: 1436,3834: 1452,3835: 1481,3836: 461,3837: 2402,3838: 794,3839: 1700,3840: 8,3841: 1584,3842: 716,3843: 3499,3844: 384,3845: 1436,3846: 1202,3847: 1443,3848: 174,3849: 2411,3850: 1094,3851: 1445,3852: 698,3853: 1443,3854: 752,3855: 2405,3856: 89,3857: 2054,3858: 1211,3859: 1460,3860: 356,3861: 3362,3862: 725,3863: 1449,3864: 422,3865: 1443,3866: 723,3867: 2417,3868: 363,3869: 1445,3870: 1436,3871: 1974,3872: 55,3873: 2426,3874: 720,3875: 1542,3876: 674,3877: 1452,3878: 933,3879: 2761,3880: 176,3881: 1454,3882: 1217,3883: 1721,3884: 365,3885: 3116,3886: 749,3887: 1581,3888: 184,3889: 1457,3890: 723,3891: 2432,3892: 476,3893: 1454,3894: 1493,3895: 1610,3896: 183,3897: 2762,3898: 729,3899: 1878,3900: 599,3901: 1562,3902: 732,3903: 2438,3904: 21,3905: 1778,3906: 1894,3907: 1466,3908: 365,3909: 2447,3910: 791,3911: 1467,3912: 311,3913: 1973,3914: 827,3915: 2877,3916: 434,3917: 1467,3918: 1223,3919: 1470,3920: 120,3921: 2456,3922: 729,3923: 1472,3924: 694,3925: 1461,3926: 744,3927: 3734,3928: 185,3929: 1472,3930: 1247,3931: 1475,3932: 369,3933: 3350,3934: 947,3935: 1478,3936: 77,3937: 1596,3938: 884,3939: 2456,3940: 363,3941: 1907,3942: 1454,3943: 1479,3944: 179,3945: 2483,3946: 738,3947: 1481,3948: 827,3949: 1760,3950: 756,3951: 2812,3952: 101,3953: 1580,3954: 1241,3955: 1901,3956: 422,3957: 2477,3958: 743,3959: 1511,3960: 416,3961: 1481,3962: 962,3963: 2477,3964: 372,3965: 1467,3966: 1238,3967: 1488,3968: 12,3969: 3926,3970: 738,3971: 1958,3972: 626,3973: 1484,3974: 746,3975: 2474,3976: 246,3977: 1487,3978: 1406,3979: 1620,3980: 375,3981: 2492,3982: 881,3983: 1919,3984: 161,3985: 1488,3986: 746,3987: 2840,3988: 372,3989: 1494,3990: 1772,3991: 1505,3992: 188,3993: 2999,3994: 747,3995: 1556,3996: 735,3997: 1934,3998: 750,3999: 2786,4000: 42,4001: 1499,4002: 1358,4003: 1502,4004: 569,4005: 2834,4006: 752,4007: 1503,4008: 317,4009: 1679,4010: 746,4011: 3257,4012: 389,4013: 1503,4014: 1435,4015: 1775,4016: 95,4017: 2558,4018: 998,4019: 1508,4020: 647,4021: 1506,4022: 755,4023: 2961,4024: 189,4025: 2106,4026: 1487,4027: 1511,4028: 416,4029: 2582,4030: 798,4031: 1532,4032: 58,4033: 1506,4034: 755,4035: 2516,4036: 377,4037: 1799,4038: 1262,4039: 1946,4040: 183,4041: 2864,4042: 827,4043: 1524,4044: 632,4045: 1511,4046: 973,4047: 2876,4048: 122,4049: 1517,4050: 1508,4051: 1520,4052: 378,4053: 3257,4054: 761,4055: 1523,4056: 314,4057: 1520,4058: 759,4059: 3407,4060: 483,4061: 1646,4062: 1268,4063: 1535,4064: 48,4065: 2558,4066: 860,4067: 2072,4068: 722,4069: 1520,4070: 896,4071: 2861,4072: 189,4073: 1526,4074: 1637,4075: 1544,4076: 383,4077: 3042,4078: 765,4079: 1530,4080: 155,4081: 2324,4082: 759,4083: 2552,4084: 381,4085: 1772,4086: 1463,4087: 1577,4088: 245,4089: 2663,4090: 761,4091: 1535,4092: 806,4093: 1533,4094: 833,4095: 3724,4097: 1532,4098: 1286,4099: 1538,4100: 374,4101: 2567,4102: 987,4103: 1817,4104: 422,4105: 1533,4106: 768,4107: 2564,4108: 393,4109: 1988,4110: 1280,4111: 1542,4112: 95,4113: 2915,4114: 926,4115: 1545,4116: 857,4117: 1697,4118: 792,4119: 2573,4120: 195,4121: 1539,4122: 1459,4123: 2339,4124: 387,4125: 3044,4126: 774,4127: 1548,4128: 86,4129: 1547,4130: 1028,4131: 3098,4132: 386,4133: 1548,4134: 1286,4135: 1553,4136: 239,4137: 3323,4138: 774,4139: 1553,4140: 796,4141: 1547,4142: 857,4143: 2588,4144: 123,4145: 1548,4146: 1301,4147: 1832,4148: 383,4149: 2938,4150: 794,4151: 2000,4152: 323,4153: 1556,4154: 854,4155: 2591,4156: 390,4157: 1557,4158: 2330,4159: 1560,4160: 18,4161: 2879,4162: 779,4163: 1695,4164: 656,4165: 2066,4166: 782,4167: 2965,4168: 194,4169: 1859,4170: 1322,4171: 1637,4172: 501,4173: 2657,4174: 783,4175: 1581,4176: 184,4177: 1565,4178: 782,4179: 3392,4180: 512,4181: 1562,4182: 1307,4183: 1634,4184: 197,4185: 3279,4186: 1095,4187: 1608,4188: 653,4189: 1670,4190: 788,4191: 3146,4192: 50,4193: 2028,4194: 1487,4195: 1575,4196: 392,4197: 2627,4198: 788,4199: 1736,4200: 419,4201: 1574,4202: 941,4203: 2993,4204: 395,4205: 1566,4206: 1313,4207: 2027,4208: 99,4209: 2858,4210: 783,4211: 1580,4212: 785,4213: 1877,4214: 1097,4215: 2630,4216: 209,4217: 1580,4218: 1457,4219: 1583,4220: 398,4221: 3962,4222: 792,4223: 1613,4224: 26,4225: 1566,4226: 791,4227: 2642,4228: 516,4229: 1584,4230: 1561,4231: 1587,4232: 216,4233: 2714,4234: 788,4235: 2446,4236: 662,4237: 1772,4238: 803,4239: 3120,4240: 93,4241: 1589,4242: 1703,4243: 1592,4244: 396,4245: 2672,4246: 941,4247: 1694,4248: 392,4249: 2055,4250: 782,4251: 2651,4252: 399,4253: 1593,4254: 1328,4255: 1728,4256: 71,4257: 3740,4258: 797,4259: 1598,4260: 683,4261: 1596,4262: 800,4263: 3533,4264: 194,4265: 1593,4266: 1611,4267: 1613,4268: 473,4269: 2672,4270: 1023,4271: 1602,4272: 167,4273: 1601,4274: 800,4275: 3347,4276: 399,4277: 2148,4278: 1547,4279: 1895,4280: 203,4281: 2681,4282: 801,4283: 1607,4284: 977,4285: 1601,4286: 804,4287: 2678,4288: 26,4289: 1607,4290: 1580,4291: 2067,4292: 396,4293: 3200,4294: 890,4295: 1613,4296: 341,4297: 1610,4298: 1043,4299: 2687,4300: 419,4301: 2072,4302: 1537,4303: 1622,4304: 99,4305: 3455,4306: 806,4307: 1670,4308: 677,4309: 1745,4310: 810,4311: 3067,4312: 317,4313: 1805,4314: 1352,4315: 1620,4316: 413,4317: 2702,4318: 821,4319: 2081,4320: 99,4321: 1614,4322: 809,4323: 3248,4324: 459,4325: 1611,4326: 1772,4327: 1623,4328: 201,4329: 3061,4330: 806,4331: 1668,4332: 755,4333: 2096,4334: 959,4335: 2702,4336: 102,4337: 1625,4338: 1538,4339: 1628,4340: 555,4341: 2717,4342: 822,4343: 1703,4344: 338,4345: 1973,4346: 809,4347: 4473,4348: 408,4349: 1629,4350: 1349,4351: 1802,4352: 5,4353: 2726,4354: 1056,4355: 1676,4356: 930,4357: 1632,4358: 818,4359: 2723,4360: 198,4361: 2168,4362: 1367,4363: 1637,4364: 410,4365: 3089,4366: 845,4367: 1934,4368: 218,4369: 1634,4370: 983,4371: 3032,4372: 408,4373: 1638,4374: 1643,4375: 2103,4376: 206,4377: 2741,4378: 980,4379: 1662,4380: 680,4381: 1637,4382: 1055,4383: 3118,4384: 50,4385: 1638,4386: 1439,4387: 1676,4388: 410,4389: 4613,4390: 825,4391: 1647,4392: 388,4393: 1809,4394: 819,4395: 2741,4396: 528,4397: 1647,4398: 1373,4399: 1688,4400: 119,4401: 3284,4402: 903,4403: 2117,4404: 692,4405: 1646,4406: 827,4407: 2750,4408: 227,4409: 1652,4410: 2071,4411: 1955,4412: 414,4413: 2762,4414: 828,4415: 1658,4416: 47,4417: 2136,4418: 864,4419: 3146,4420: 395,4421: 1656,4422: 1688,4423: 1659,4424: 273,4425: 2858,4426: 828,4427: 1835,4428: 818,4429: 1772,4430: 833,4431: 3596,4432: 102,4433: 2090,4434: 1391,4435: 1665,4436: 414,4437: 3140,4438: 1068,4439: 1808,4440: 341,4441: 1664,4442: 831,4443: 2777,4444: 491,4445: 2175,4446: 1742,4447: 1668,4448: 53,4449: 2786,4450: 824,4451: 1670,4452: 893,4453: 1664,4454: 848,4455: 3929,4456: 207,4457: 1670,4458: 1397,4459: 2226,4460: 420,4461: 2792,4462: 908,4463: 1674,4464: 211,4465: 1928,4466: 1271,4467: 2792,4468: 417,4469: 1670,4470: 1391,4471: 1688,4472: 218,4473: 4189,4474: 837,4475: 1694,4476: 698,4477: 2011,4478: 840,4479: 2798,4480: 15,4481: 1679,4482: 1694,4483: 1682,4484: 482,4485: 3041,4486: 842,4487: 2162,4488: 419,4489: 1735,4490: 836,4491: 3197,4492: 422,4493: 1683,4494: 1841,4495: 1788,4496: 104,4497: 2816,4498: 837,4499: 1994,4500: 793,4501: 2177,4502: 845,4503: 3191,4504: 212,4505: 1670,4506: 1412,4507: 1691,4508: 609,4509: 3360,4510: 995,4511: 1700,4512: 92,4513: 1691,4514: 840,4515: 3797,4516: 422,4517: 1692,4518: 1616,4519: 1695,4520: 206,4521: 3344,4522: 1205,4523: 1697,4524: 701,4525: 1686,4526: 902,4527: 3220,4528: 107,4529: 2190,4530: 1433,4531: 1845,4532: 512,4533: 2837,4534: 851,4535: 1703,4536: 545,4537: 1695,4538: 849,4539: 2837,4540: 428,4541: 1898,4542: 1418,4543: 2678,4544: 27,4545: 3214,4546: 851,4547: 1706,4548: 716,4549: 1704,4550: 1086,4551: 2840,4552: 212,4553: 1701,4554: 2075,4555: 1710,4556: 440,4557: 4022,4558: 893,4559: 1781,4560: 197,4561: 1709,4562: 854,4563: 3357,4564: 557,4565: 2072,4566: 1427,4567: 1713,4568: 215,4569: 2861,4570: 851,4571: 2202,4572: 823,4573: 1709,4574: 858,4575: 2849,4576: 62,4577: 1884,4578: 1838,4579: 1898,4580: 423,4581: 3244,4582: 879,4583: 1719,4584: 362,4585: 2243,4586: 858,4587: 3443,4588: 456,4589: 1715,4590: 1688,4591: 1722,4592: 137,4593: 2876,4594: 860,4595: 1725,4596: 722,4597: 1722,4598: 1145,4599: 4190,4600: 231,4601: 1841,4602: 1487,4603: 1727,4604: 432,4605: 2897,4606: 1194,4607: 1739,4608: 7,4609: 2054,4610: 858,4611: 2876,4612: 431,4613: 2231,4614: 1442,4615: 1773,4616: 215,4617: 3827,4618: 864,4619: 1842,4620: 1097,4621: 1731,4622: 867,4623: 3236,4624: 106,4625: 1719,4626: 1640,4627: 2229,4628: 428,4629: 2897,4630: 870,4631: 2051,4632: 362,4633: 1733,4634: 1124,4635: 3346,4636: 479,4637: 1737,4638: 1448,4639: 1740,4640: 48,4641: 3725,4642: 1040,4643: 1742,4644: 899,4645: 1736,4646: 945,4647: 2903,4648: 287,4649: 1742,4650: 1544,4651: 1745,4652: 437,4653: 4064,4654: 881,4655: 2558,4656: 182,4657: 1745,4658: 869,4659: 2912,4660: 431,4661: 1853,4662: 2122,4663: 1749,4664: 257,4665: 2933,4666: 873,4667: 1758,4668: 728,4669: 2445,4670: 878,4671: 3438,4672: 26,4673: 1751,4674: 1619,4675: 2063,4676: 570,4677: 2927,4678: 878,4679: 1755,4680: 409,4681: 1893,4682: 876,4683: 3797,4684: 440,4685: 1751,4686: 1781,4687: 1838,4688: 108,4689: 3323,4690: 1163,4691: 1760,4692: 797,4693: 1954,4694: 881,4695: 2930,4696: 221,4697: 2675,4698: 1751,4699: 1788,4700: 456,4701: 2942,4702: 882,4703: 1764,4704: 122,4705: 1758,4706: 876,4707: 3350,4708: 533,4709: 1760,4710: 1466,4711: 2270,4712: 260,4713: 2951,4714: 882,4715: 1916,4716: 851,4717: 1763,4718: 1136,4719: 3536,4720: 113,4721: 1769,4722: 1481,4723: 1772,4724: 441,4725: 4470,4726: 899,4727: 1793,4728: 368,4729: 1772,4730: 1097,4731: 3353,4732: 567,4733: 1773,4734: 1690,4735: 1778,4736: 12,4737: 2966,4738: 984,4739: 2283,4740: 758,4741: 2111,4742: 890,4743: 3578,4744: 221,4745: 1760,4746: 1907,4747: 1854,4748: 446,4749: 2972,4750: 980,4751: 1782,4752: 263,4753: 2363,4754: 890,4755: 2966,4756: 440,4757: 1889,4758: 1481,4759: 1785,4760: 281,4761: 3679,4762: 891,4763: 2111,4764: 743,4765: 1781,4766: 894,4767: 3866,4768: 54,4769: 1994,4770: 1684,4771: 1797,4772: 446,4773: 3122,4774: 1448,4775: 1806,4776: 377,4777: 1787,4778: 894,4779: 3689,4780: 450,4781: 2312,4782: 1493,4783: 1794,4784: 120,4785: 3530,4786: 896,4787: 1796,4788: 1208,4789: 1794,4790: 900,4791: 2993,4792: 225,4793: 1796,4794: 1562,4795: 2306,4796: 530,4797: 3395,4798: 900,4799: 1800,4800: 44,4801: 1799,4802: 1200,4803: 3002,4804: 449,4805: 1920,4806: 1772,4807: 2561,4808: 224,4809: 3863,4810: 882,4811: 1817,4812: 752,4813: 1803,4814: 923,4815: 3476,4816: 152,4817: 1805,4818: 1784,4819: 1851,4820: 446,4821: 3017,4822: 905,4823: 2319,4824: 443,4825: 1799,4826: 1016,4827: 3017,4828: 464,4829: 2150,4830: 2108,4831: 1812,4832: 57,4833: 3602,4834: 905,4835: 1815,4836: 803,4837: 2339,4838: 938,4839: 3023,4840: 271,4841: 1929,4842: 1714,4843: 1836,4844: 582,4845: 3347,4846: 909,4847: 1844,4848: 188,4849: 1812,4850: 899,4851: 5390,4852: 453,4853: 1997,4854: 1517,4855: 1823,4856: 228,4857: 3041,4858: 1178,4859: 1907,4860: 910,4861: 1821,4862: 1073,4863: 3038,4864: 8,4865: 2378,4866: 1526,4867: 1941,4868: 455,4869: 3448,4870: 915,4871: 1827,4872: 488,4873: 2171,4874: 912,4875: 3032,4876: 495,4877: 1827,4878: 1741,4879: 2348,4880: 108,4881: 3056,4882: 914,4883: 2024,4884: 902,4885: 1826,4886: 1176,4887: 3597,4888: 237,4889: 1832,4890: 1547,4891: 1889,4892: 459,4893: 3932,4894: 918,4895: 2165,4896: 110,4897: 1946,4898: 1002,4899: 3422,4900: 606,4901: 1827,4902: 1778,4903: 1839,4904: 228,4905: 3469,4906: 1097,4907: 2364,4908: 767,4909: 1839,4910: 923,4911: 3068,4912: 116,4913: 1839,4914: 2325,4915: 1845,4916: 459,4917: 3632,4918: 923,4919: 1845,4920: 380,4921: 2621,4922: 1022,4923: 3503,4924: 462,4925: 1836,4926: 1538,4927: 1856,4928: 44,4929: 3278,4930: 905,4931: 1850,4932: 875,4933: 1848,4934: 926,4935: 4133,4936: 230,4937: 1850,4938: 1547,4939: 2189,4940: 506,4941: 3683,4942: 1190,4943: 1854,4944: 197,4945: 2108,4946: 926,4947: 3092,4948: 462,4949: 2460,4950: 2072,4951: 1857,4952: 233,4953: 3143,4954: 927,4955: 1860,4956: 1031,4957: 1857,4958: 956,4959: 3884,4960: 60,4961: 2231,4962: 1556,4963: 2391,4964: 461,4965: 3122,4966: 939,4967: 1863,4968: 498,4969: 1862,4970: 1230,4971: 3107,4972: 551,4973: 1863,4974: 1553,4975: 1881,4976: 117,4977: 4648,4978: 1049,4979: 1875,4980: 797,4981: 1862,4982: 972,4983: 3731,4984: 299,4985: 1863,4986: 1765,4987: 1871,4988: 488,4989: 3122,4990: 938,4991: 2784,4992: 23,4993: 1871,4994: 1118,4995: 3672,4996: 467,4997: 2087,4998: 2072,4999: 1875,5000: 228,}

if __name__ == '__main__':
    n = int(input()) + 1
    
    total = 0

    for k, v in res.items():
        if k < n:
            total += v
        else:
            break
            
    
    print(total)