0     1
   1    10
   2     5
   3    10
   4    10
   5     2
   6     5
   7    10
   8    10
   9    10
  10     3
  11    10
  12     5
  13    10
  14    10
  15     2
  16    10
  17    10
  18    10
  19    10
  20     5
  21    10
  22     5
  23    10
  24     5
  25     8
  26     5
  27    10
  28     5
  29    10
  30     8
  31    10
  32    10
  33    10
  34    10
  35     4
  36     5
  37    10
  38    10
  39    10
  40     7
  41    10
  42    10
  43    10
  44     5
  45     2
  46    10
  47    10
  48     5
  49    10
  50     7
  51    10
  52     5
  53    10
  54     5
  55     4
  56    10
  57    10
  58    10
  59    10
  60     7
  61    10
  62    10
  63    10
  64    10
  65     2
  66     5
  67    10
  68     5
  69    10
  70     9
  71    10
  72     5
  73    10
  74     5
  75     6
  76     5
  77    10
  78    10
  79    10
  80     8
  81    10
  82    10
  83    10
  84    10
  85     8
  86    10
  87    10
  88    10
  89    10
  90     8
  91    10
  92     5
  93    10
  94     5
  95     8
  96    10
  97    10
  98    10
  99    10
 100     5
 101    10
 102    10
 103    10
 104    10
 105     8
 106    10
 107    10
 108     5
 109    10
 110     6
 111    10
 112     5
 113    10
 114     5
 115     2
 116    10
 117    10
 118     5
 119    10
 120    10
 121    10
 122    10
 123    10
 124     5
 125     4
 126    10
 127    10
 128    10
 129    10
 130     1
 131    10
 132     5
 133    10
 134     5
 135     4
 136    10
 137    10
 138    10
 139    10
 140     5
 141    10
 142     5
 143    10
 144     5
 145     6
 146    10
 147    10
 148     5
 149    10
 150     5
 151    10
 152    10
 153    10
 154     5
 155    10
 156     5
 157    10
 158    10
 159    10
 160     4
 161    10
 162    10
 163    10
 164    10
 165     4
 166     5
 167    10
 168     5
 169    10
 170     6
 171    10
 172    10
 173    10
 174     5
 175    10
 176    10
 177    10
 178     5
 179    10
 180     8
 181    10
 182    10
 183    10
 184    10
 185     4
 186     5
 187    10
 188     5
 189    10
 190     2
 191    10
 192     5
 193    10
 194     5
 195     8
 196     5
 197    10
 198    10
 199    10
 200     3
 201    10
 202     5
 203    10
 204    10
 205    10
 206     5
 207    10
 208    10
 209    10
 210     6
 211    10
 212     5
 213    10
 214    10
 215    10
 216    10
 217    10
 218    10
 219    10
 220     2
 221    10
 222    10
 223    10
 224     5
 225     8
 226    10
 227    10
 228     5
 229    10
 230     2
 231    10
 232     5
 233    10
 234    10
 235     6
 236    10
 237    10
 238    10
 239    10
 240     6
 241    10
 242    10
 243    10
 244    10
 245     4
 246     5
 247    10
 248    10
 249    10
 250     2
 251    10
 252    10
 253    10
 254    10
 255    10
 256     5
 257    10
 258     5
 259    10
 260     4
 261    10
 262     5
 263    10
 264     5
 265     8
 266    10
 267    10
 268    10
 269    10
 270     4
 271    10
 272    10
 273    10
 274     5
 275    10
 276     5
 277    10
 278     5
 279    10
 280     3
 281    10
 282     5
 283    10
 284     5
 285     2
 286    10
 287    10
 288    10
 289    10
 290     6
 291    10
 292    10
 293    10
 294    10
 295     2
 296    10
 297    10
 298    10
 299    10
 300     4
 301    10
 302    10
 303    10
 304     5
 305     2
 306     5
 307    10
 308     5
 309    10
 310     3
 311    10
 312    10
 313    10
 314    10
 315     8
 316     5
 317    10
 318     5
 319    10
 320    10
 321    10
 322    10
 323    10
 324     5
 325    10
 326     5
 327    10
 328    10
 329    10
 330     3
 331    10
 332     5
 333    10
 334    10
 335     6
 336     5
 337    10
 338     5
 339    10
 340    10
 341    10
 342    10
 343    10
 344    10
 345    10
 346    10
 347    10
 348     5
 349    10
 350     6
 351    10
 352    10
 353    10
 354     5
 355     8
 356     5
 357    10
 358     5
 359    10
 360     5
 361    10
 362     5
 363    10
 364     5
 365     8
 366     5
 367    10
 368    10
 369    10
 370     6
 371    10
 372     5
 373    10
 374    10
 375     4
 376    10
 377    10
 378    10
 379    10
 380    10
 381    10
 382    10
 383    10
 384    10
 385     2
 386    10
 387    10
 388    10
 389    10
 390     2
 391    10
 392    10
 393    10
 394    10
 395     4
 396    10
 397    10
 398    10
 399    10
 400     8
 401    10
 402     5
 403    10
 404     5
 405     2
 406     5
 407    10
 408     5
 409    10
 410    10
 411    10
 412     5
 413    10
 414    10
 415     4
 416    10
 417    10
 418     5
 419    10
 420     9
 421    10
 422     5
 423    10
 424    10
 425     6
 426    10
 427    10
 428     5
 429    10
 430     1
 431    10
 432    10
 433    10
 434    10
 435     6
 436    10
 437    10
 438     5
 439    10
 440     5
 441    10
 442     5
 443    10
 444    10
 445    10
 446    10
 447    10
 448    10
 449    10
 450     9
 451    10
 452     5
 453    10
 454    10
 455     8
 456    10
 457    10
 458    10
 459    10
 460    2
 461    10
 462      5
 463    10
 464     5
 465     8
 466    10
 467    10
 468     5
 469    10
 470    10
 471    10
 472    10
 473    10
 474     5
 475     4
 476    10
 477    10
 478    10
 479    10
 480     7
 481    10
 482    10
 483    10
 484     5
 485     8
 486     5
 487    10
 488     5
 489    10
 490     2
 491    10
 492    10
 493    10
 494    10
 495     8
 496     5
 497    10
 498    10
 499    10
 500    10
 501    10
 502     5
 503    10
 504    10
 505     6
 506     5
 507    10
 508     5
 509    10
 510     3
 511    10
 512     5
 513    10
 514    10
 515    10
 516     5
 517    10
 518     5
 519    10
 520     5
 521    10
 522    10
 523    10
 524     5
 525     6
 526     5
 527    10
 528    10
 529    10
 530     2
 531    10
 532    10
 533    10
 534     5
 535     6
 536    10
 537    10
 538    10
 539    10
 540     7
 541    10
 542     5
 543    10
 544    10
 545     2
 546     5
 547    10
 548    10
 549    10
 550     3
 551    10
 552    10
 553    10
 554    10
 555     4
 556     5
 557    10
 558    10
 559    10
 560     2
 561    10
 562    10
 563    10
 564     5
 565    10
 566    10
 567    10
 568    10
 569    10
 570     7
 571    10
 572    10
 573    10
 574     5
 575     2
 576     5
 577    10
 578     5
 579    10
 580     7
 581    10
 582    10
 583    10
 584     5
 585     2
 586     5
 587    10
 588    10
 589    10
 590     7
 591    10
 592    10
 593    10
 594     5
 595     4
 596    10
 597    10
 598    10
 599    10
 600    10
 601    10
 602     5
 603    10
 604     5
 605    10
 606    10
 607    10
 608     5
 609    10
 610     5
 611    10
 612    10
 613    10
 614    10
 615    10
 616    10
 617    10
 618     5
 619    10
 620     5
 621    10
 622    10
 623    10
 624    10
 625     4
 626     5
 627    10
 628    10
 629    10
 630     9
 631    10
 632    10
 633    10
 634    10
 635     6
 636     5
 637    10
 638    10
 639    10
 640     1
 641    10
 642     5
 643    10
 644    10
 645     4
 646    10
 647    10
 648    10
 649    10
 650     4
 651    10
 652    10
 653    10
 654    10
 655     4
 656    10
 657    10
 658     5
 659    10
 660     4
 661    10
 662    10
 663    10
 664    10
 665     8
 666     5
 667    10
 668    10
 669    10
 670     9
 671    10
 672     5
 673    10
 674     5
 675    10
 676    10
 677    10
 678    10
 679    10
 680     9
 681    10
 682    10
 683    10
 684     5
 685    10
 686    10
 687    10
 688    10
 689    10
 690     2
 691    10
 692     5
 693    10
 694    10
 695     2
 696    10
 697    10
 698     5
 699    10
 700     7
 701    10
 702     5
 703    10
 704     5
 705     4
 706     5
 707    10
 708     5
 709    10
 710     4
 711    10
 712    10
 713    10
 714     5
 715     4
 716     5
 717    10
 718    10
 719    10
 720     2
 721    10
 722     5
 723    10
 724     5
 725     6
 726    10
 727    10
 728    10
 729    10
 730     2
 731    10
 732    10
 733    10
 734     5
 735     6
 736     5
 737    10
 738     5
 739    10
 740     7
 741    10
 742    10
 743    10
 744     5
 745     2
 746    10
 747    10
 748     5
 749    10
 750     7
 751    10
 752    10
 753    10
 754    10
 755    10
 756     5
 757    10
 758     5
 759    10
 760     5
 761    10
 762     5
 763    10
 764    10
 765     8
 766    10
 767    10
 768     5
 769    10
 770    10
 771    10
 772     5
 773    10
 774     5
 775     8
 776     5
 777    10
 778    10
 779    10
 780     4
 781    10
 782    10
 783    10
 784     5
 785     6
 786    10
 787    10
 788    10
 789    10
 790     5
 791    10
 792     5
 793    10
 794    10
 795     8
 796    10
 797    10
 798    10
 799    10
 800     2
 801    10
 802    10
 803    10
 804     5
 805     2
 806     5
 807    10
 808    10
 809    10
 810     8
 811    10
 812     5
 813    10
 814    10
 815     4
 816     5
 817    10
 818     5
 819    10
 820     2
 821    10
 822    10
 823    10
 824     5
 825     4
 826    10
 827    10
 828     5
 829    10
 830     7
 831    10
 832    10
 833    10
 834    10
 835     6
 836    10
 837    10
 838     5
 839    10
 840     1
 841    10
 842     5
 843    10
 844     5
 845     8
 846    10
 847    10
 848     5
 849    10
 850     2
 851    10
 852    10
 853    10
 854     5
 855     6
 856    10
 857    10
 858    10
 859    10
 860     3
 861    10
 862    10
 863    10
 864     5
 865    10
 866     5
 867    10
 868    10
 869    10
 870     6
 871    10
 872    10
 873    10
 874     5
 875     2
 876    10
 877    10
 878     5
 879    10
 880     6
 881    10
 882     5
 883    10
 884     5
 885     4
 886    10
 887    10
 888     5
 889    10
 890     4
 891    10
 892    10
 893    10
 894    10
 895     8
 896     5
 897    10
 898    10
 899    10
 900     4
 901    10
 902     5
 903    10
 904     5
 905     8
 906    10
 907    10
 908    10
 909    10
 910    10
 911    10
 912     5
 913    10
 914     5
 915     2
 916    10
 917    10
 918     5
 919    10
 920     5
 921    10
 922    10
 923    10
 924     5
 925     6
 926    10
 927    10
 928    10
 929    10
 930     1
 931    10
 932     5
 933    10
 934    10
 935     6
 936    10
 937    10
 938    10
 939    10
 940     2
 941    10
 942    10
 943    10
 944    10
 945     2
 946     5
 947    10
 948    10
 949    10
 950    10
 951    10
 952    10
 953    10
 954    10
 955    10
 956    10
 957    10
 958    10
 959    10
 960     1
 961    10
 962    10
 963    10
 964    10
 965     4
 966    10
 967    10
 968     5
 969    10
 970     8
 971    10
 972     5
 973    10
 974    10
 975     2
 976    10
 977    10
 978     5
 979    10
 980     9
 981    10
 982     5
 983    10
 984     5
 985     6
 986    10
 987    10
 988     5
 989    10
 990     3
 991    10
 992    10
 993    10
 994    10
 995     4
 996     5
 997    10
 998    10
 999    10
1000    10
1001    10
1002     5
1003    10
1004    10
1005     2
1006     5
1007    10
1008     5
1009    10
1010     1
1011    10
1012     5
1013    10
1014    10
1015     8
1016     5
1017    10
1018    10
1019    10
1020     8
1021    10
1022    10
1023    10
1024     5
1025     8
1026    10
1027    10
1028    10
1029    10
1030     9
1031    10
1032    10
1033    10
1034    10
1035     4
1036     5
1037    10
1038     5
1039    10
1040     2
1041    10
1042    10
1043    10
1044     5
1045     2
1046    10
1047    10
1048    10
1049    10
1050     4
1051    10
1052     5
1053    10
1054     5
1055     2
1056     5
1057    10
1058     5
1059    10
1060     6
1061    10
1062     5
1063    10
1064    10
1065     8
1066    10
1067    10
1068    10
1069    10
1070     9
1071    10
1072    10
1073    10
1074     5
1075    10
1076     5
1077    10
1078     5
1079    10
1080    10
1081    10
1082     5
1083    10
1084     5
1085     2
1086     5
1087    10
1088    10
1089    10
1090     9
1091    10
1092    10
1093    10
1094     5
1095     4
1096    10
1097    10
1098    10
1099    10
1100     9
1101    10
1102    10
1103    10
1104    10
1105     8
1106     5
1107    10
1108    10
1109    10
1110     9
1111    10
1112     5
1113    10
1114    10
1115     6
1116     5
1117    10
1118    10
1119    10
1120     7
1121    10
1122     5
1123    10
1124     5
1125     4
1126     5
1127    10
1128    10
1129    10
1130     9
1131    10
1132     5
1133    10
1134    10
1135    10
1136     5
1137    10
1138     5
1139    10
1140     1
1141    10
1142     5
1143    10
1144     5
1145     8
1146     5
1147    10
1148    10
1149    10
1150    10
1151    10
1152     5
1153    10
1154     5
1155     8
1156     5
1157    10
1158    10
1159    10
1160     1
1161    10
1162     5
1163    10
1164    10
1165     6
1166     5
1167    10
1168     5
1169    10
1170     4
1171    10
1172     5
1173    10
1174    10
1175     6
1176    10
1177    10
1178    10
1179    10
1180     1
1181    10
1182     5
1183    10
1184    10
1185     2
1186    10
1187    10
1188     5
1189    10
1190     2
1191    10
1192     5
1193    10
1194    10
1195     6
1196     5
1197    10
1198     5
1199    10
1200     9
1201    10
1202     5
1203    10
1204     5
1205     6
1206    10
1207    10
1208    10
1209    10
1210     7
1211    10
1212    10
1213    10
1214     5
1215     8
1216     5
1217    10
1218     5
1219    10
1220     9
1221    10
1222     5
1223    10
1224    10
1225     4
1226    10
1227    10
1228     5
1229    10
1230     4
1231    10
1232    10
1233    10
1234    10
1235     4
1236    10
1237    10
1238    10
1239    10
1240     1
1241    10
1242    10
1243    10
1244    10
1245     2
1246     5
1247    10
1248    10
1249    10
1250     8
1251    10
1252    10
1253    10
1254     5
1255     6
1256    10
1257    10
1258     5
1259    10
1260     1
1261    10
1262     5
1263    10
1264    10
1265    10
1266     5
1267    10
1268     5
1269    10
1270     8
1271    10
1272     5
1273    10
1274    10
1275    10
1276    10
1277    10
1278     5
1279    10
1280     9
1281    10
1282     5
1283    10
1284     5
1285     8
1286    10
1287    10
1288    10
1289    10
1290     7
1291    10
1292    10
1293    10
1294    10
1295     2
1296    10
1297    10
1298    10
1299    10
1300     8
1301    10
1302     5
1303    10
1304    10
1305     8
1306     5
1307    10
1308     5
1309    10
1310     5
1311    10
1312    10
1313    10
1314    10
1315     6
1316    10
1317    10
1318     5
1319    10
1320     4
1321    10
1322     5
1323    10
1324     5
1325     6
1326    10
1327    10
1328     5
1329    10
1330     3
1331    10
1332     5
1333    10
1334    10
1335     2
1336     5
1337    10
1338    10
1339    10
1340     1
1341    10
1342     5
1343    10
1344     5
1345     4
1346     5
1347    10
1348    10
1349    10
1350     2
1351    10
1352    10
1353    10
1354     5
1355    10
1356    10
1357    10
1358     5
1359    10
1360     4
1361    10
1362     5
1363    10
1364    10
1365     4
1366    10
1367    10
1368    10
1369    10
1370     5
1371    10
1372     5
1373    10
1374    10
1375    10
1376     5
1377    10
1378     5
1379    10
1380     9
1381    10
1382    10
1383    10
1384     5
1385     2
1386    10
1387    10
1388    10
1389    10
1390     9
1391    10
1392     5
1393    10
1394     5
1395     8
1396    10
1397    10
1398     5
1399    10
1400     7
1401    10
1402    10
1403    10
1404     5
1405     4
1406     5
1407    10
1408     5
1409    10
1410     3
1411    10
1412     5
1413    10
1414     5
1415     4
1416     5
1417    10
1418     5
1419    10
1420     7
1421    10
1422    10
1423    10
1424    10
1425     4
1426    10
1427    10
1428     5
1429    10
1430     4
1431    10
1432    10
1433    10
1434    10
1435     8
1436    10
1437    10
1438     5
1439    10
1440     4
1441    10
1442     5
1443    10
1444     5
1445     4
1446     5
1447    10
1448    10
1449    10
1450     9
1451    10
1452     5
1453    10
1454     5
1455     8
1456    10
1457    10
1458    10
1459    10
1460     6
1461    10
1462    10
1463    10
1464    10
1465     2
1466     5
1467    10
1468     5
1469    10
1470    10
1471    10
1472    10
1473    10
1474     5
1475     2
1476    10
1477    10
1478     5
1479    10
1480     6
1481    10
1482     5
1483    10
1484     5
1485     8
1486    10
1487    10
1488     5
1489    10
1490     2
1491    10
1492    10
1493    10
1494    10
1495     6
1496     5
1497    10
1498    10
1499    10
1500     3
1501    10
1502     5
1503    10
1504    10
1505    10
1506     5
1507    10
1508     5
1509    10
1510     9
1511    10
1512     5
1513    10
1514    10
1515     6
1516    10
1517    10
1518    10
1519    10
1520     8
1521    10
1522     5
1523    10
1524     5
1525     6
1526     5
1527    10
1528    10
1529    10
1530     2
1531    10
1532     5
1533    10
1534    10
1535     6
1536     5
1537    10
1538     5
1539    10
1540     7
1541    10
1542     5
1543    10
1544    10
1545     2
1546    10
1547    10
1548    10
1549    10
1550     8
1551    10
1552     5
1553    10
1554     5
1555     4
1556    10
1557    10
1558    10
1559    10
1560     9
1561    10
1562     5
1563    10
1564     5
1565     4
1566     5
1567    10
1568     5
1569    10
1570     1
1571    10
1572    10
1573    10
1574     5
1575     2
1576    10
1577    10
1578    10
1579    10
1580     5
1581    10
1582     5
1583    10
1584    10
1585     2
1586     5
1587    10
1588     5
1589    10
1590     8
1591    10
1592    10
1593    10
1594    10
1595     4
1596    10
1597    10
1598    10
1599    10
1600     1
1601    10
1602     5
1603    10
1604     5
1605     4
1606     5
1607    10
1608     5
1609    10
1610     2
1611    10
1612    10
1613    10
1614    10
1615     6
1616    10
1617    10
1618    10
1619    10
1620     5
1621    10
1622     5
1623    10
1624     5
1625     4
1626    10
1627    10
1628     5
1629    10
1630     4
1631    10
1632     5
1633    10
1634    10
1635     4
1636    10
1637    10
1638     5
1639    10
1640     4
1641    10
1642     5
1643    10
1644     5
1645     6
1646     5
1647    10
1648    10
1649    10
1650     6
1651    10
1652     5
1653    10
1654     5
1655     8
1656    10
1657    10
1658    10
1659    10
1660     7
1661    10
1662     5
1663    10
1664    10
1665    10
1666     5
1667    10
1668     5
1669    10
1670     3
1671    10
1672     5
1673    10
1674    10
1675     8
1676    10
1677    10
1678    10
1679    10
1680     3
1681    10
1682    10
1683    10
1684    10
1685     4
1686     5
1687    10
1688    10
1689    10
1690     4
1691    10
1692     5
1693    10
1694     5
1695     4
1696    10
1697    10
1698    10
1699    10
1700     7
1701    10
1702    10
1703    10
1704    10
1705     2
1706    10
1707    10
1708    10
1709    10
1710     6
1711    10
1712    10
1713    10
1714    10
1715    10
1716    10
1717    10
1718     5
1719    10
1720     6
1721    10
1722    10
1723    10
1724    10
1725    10
1726     5
1727    10
1728     5
1729    10
1730     9
1731    10
1732    10
1733    10
1734    10
1735    10
1736    10
1737    10
1738    10
1739    10
1740    10
1741    10
1742     5
1743    10
1744    10
1745     8
1746     5
1747    10
1748     5
1749    10
1750     4
1751    10
1752     5
1753    10
1754    10
1755     8
1756     5
1757    10
1758    10
1759    10
1760     3
1761    10
1762    10
1763    10
1764     5
1765     4
1766    10
1767    10
1768    10
1769    10
1770     6
1771    10
1772    10
1773    10
1774    10
1775     2
1776    10
1777    10
1778     5
1779    10
1780     2
1781    10
1782     5
1783    10
1784     5
1785     6
1786     5
1787    10
1788     5
1789    10
1790     7
1791    10
1792    10
1793    10
1794     5
1795     2
1796    10
1797    10
1798     5
1799    10
1800     6
1801    10
1802    10
1803    10
1804    10
1805     8
1806     5
1807    10
1808    10
1809    10
1810     2
1811    10
1812    10
1813    10
1814    10
1815     2
1816    10
1817    10
1818     5
1819    10
1820     1
1821    10
1822     5
1823    10
1824    10
1825    10
1826    10
1827    10
1828     5
1829    10
1830     3
1831    10
1832    10
1833    10
1834     5
1835     4
1836    10
1837    10
1838     5
1839    10
1840     6
1841    10
1842    10
1843    10
1844    10
1845     6
1846     5
1847    10
1848     5
1849    10
1850     6
1851    10
1852     5
1853    10
1854    10
1855     8
1856    10
1857    10
1858    10
1859    10
1860     6
1861    10
1862     5
1863    10
1864     5
1865     6
1866    10
1867    10
1868    10
1869    10
1870     8
1871    10
1872     5
1873    10
1874     5
1875     8
1876     5
1877    10
1878    10
1879    10
1880     9
1881    10
1882     5
1883    10
1884     5
1885    10
1886     5
1887    10
1888    10
1889    10
1890     4
1891    10
1892     5
1893    10
1894     5
1895     4
1896     5
1897    10
1898    10
1899    10
1900     7
1901    10
1902    10
1903    10
1904    10
1905    10
1906    10
1907    10
1908     5
1909    10
1910     7
1911    10
1912     5
1913    10
1914    10
1915     4
1916     5
1917    10
1918    10
1919    10
1920     5
1921    10
1922    10
1923    10
1924    10
1925     4
1926     5
1927    10
1928    10
1929    10
1930     2
1931    10
1932    10
1933    10
1934    10
1935     6
1936     5
1937    10
1938     5
1939    10
1940     9
1941    10
1942     5
1943    10
1944    10
1945     6
1946     5
1947    10
1948    10
1949    10
1950     2
1951    10
1952    10
1953    10
1954     5
1955     6
1956     5
1957    10
1958     5
1959    10
1960     6
1961    10
1962    10
1963    10
1964     5
1965     4
1966    10
1967    10
1968    10
1969    10
1970     7
1971    10
1972     5
1973    10
1974     5
1975     4
1976    10
1977    10
1978    10
1979    10
1980     5
1981    10
1982    10
1983    10
1984    10
1985     8
1986     5
1987    10
1988     5
1989    10
1990     9
1991    10
1992     5
1993    10
1994     5
1995     6
1996     5
1997    10
1998    10
1999    10
2000     5
2001    10
2002    10
2003    10
2004     5
2005     2
2006     5
2007    10
2008    10
2009    10
2010     6
2011    10
2012     5
2013    10
2014    10
2015     8
2016    10
2017    10
2018     5
2019    10
2020     3
2021    10
2022    10
2023    10
2024     5
2025     4
2026     5
2027    10
2028     5
2029    10
2030     2
2031    10
2032    10
2033    10
2034    10
2035     8
2036    10
2037    10
2038    10
2039    10
2040     8
2041    10
2042     5
2043    10
2044    10
2045     2
2046     5
2047    10
2048    10
2049    10
2050     6
2051    10
2052    10
2053    10
2054     5
2055     6
2056     5
2057    10
2058    10
2059    10
2060     2
2061    10
2062    10
2063    10
2064     5
2065     2
2066    10
2067    10
2068     5
2069    10
2070     1
2071    10
2072     5
2073    10
2074    10
2075     8
2076    10
2077    10
2078     5
2079    10
2080     2
2081    10
2082    10
2083    10
2084     5
2085     2
2086    10
2087    10
2088     5
2089    10
2090     2
2091    10
2092     5
2093    10
2094    10
2095    10
2096    10
2097    10
2098     5
2099    10
2100     8
2101    10
2102     5
2103    10
2104     5
2105     4
2106     5
2107    10
2108     5
2109    10
2110     8
2111    10
2112    10
2113    10
2114     5
2115     8
2116     5
2117    10
2118    10
2119    10
2120    10
2121    10
2122    10
2123    10
2124    10
2125     6
2126    10
2127    10
2128     5
2129    10
2130     5
2131    10
2132     5
2133    10
2134    10
2135    10
2136     5
2137    10
2138    10
2139    10
2140     1
2141    10
2142    10
2143    10
2144     5
2145    10
2146     5
2147    10
2148     5
2149    10
2150     9
2151    10
2152    10
2153    10
2154     5
2155     6
2156    10
2157    10
2158     5
2159    10
2160     5
2161    10
2162     5
2163    10
2164     5
2165     2
2166    10
2167    10
2168    10
2169    10
2170     1
2171    10
2172    10
2173    10
2174    10
2175     2
2176    10
2177    10
2178     5
2179    10
2180     2
2181    10
2182     5
2183    10
2184    10
2185     6
2186     5
2187    10
2188    10
2189    10
2190     9
2191    10
2192     5
2193    10
2194     5
2195     6
2196    10
2197    10
2198     5
2199    10
2200     7
2201    10
2202    10
2203    10
2204     5
2205    10
2206     5
2207    10
2208     5
2209    10
2210     5
2211    10
2212     5
2213    10
2214    10
2215     8
2216     5
2217    10
2218     5
2219    10
2220     4
2221    10
2222     5
2223    10
2224     5
2225     2
2226    10
2227    10
2228    10
2229    10
2230     9
2231    10
2232     5
2233    10
2234     5
2235     4
2236     5
2237    10
2238    10
2239    10
2240     5
2241    10
2242     5
2243    10
2244    10
2245    10
2246     5
2247    10
2248     5
2249    10
2250     3
2251    10
2252    10
2253    10
2254    10
2255     4
2256    10
2257    10
2258     5
2259    10
2260    10
2261    10
2262     5
2263    10
2264     5
2265     4
2266    10
2267    10
2268     5
2269    10
2270    10
2271    10
2272    10
2273    10
2274     5
2275     2
2276    10
2277    10
2278    10
2279    10
2280     2
2281    10
2282    10
2283    10
2284    10
2285    10
2286     5
2287    10
2288     5
2289    10
2290     5
2291    10
2292    10
2293    10
2294    10
2295     4
2296    10
2297    10
2298    10
2299    10
2300     3
2301    10
2302    10
2303    10
2304     5
2305     6
2306     5
2307    10
2308     5
2309    10
2310     8
2311    10
2312    10
2313    10
2314     5
2315    10
2316    10
2317    10
2318     5
2319    10
2320     7
2321    10
2322     5
2323    10
2324    10
2325     4
2326     5
2327    10
2328     5
2329    10
2330     2
2331    10
2332     5
2333    10
2334    10
2335     6
2336    10
2337    10
2338    10
2339    10
2340     1
2341    10
2342    10
2343    10
2344    10
2345     6
2346    10
2347    10
2348     5
2349    10
2350     2
2351    10
2352     5
2353    10
2354     5
2355    10
2356     5
2357    10
2358     5
2359    10
2360     3
2361    10
2362    10
2363    10
2364    10
2365     4
2366     5
2367    10
2368     5
2369    10
2370     1
2371    10
2372     5
2373    10
2374     5
2375    10
2376     5
2377    10
2378     5
2379    10
2380     3
2381    10
2382     5
2383    10
2384     5
2385    10
2386    10
2387    10
2388    10
2389    10
2390    10
2391    10
2392     5
2393    10
2394    10
2395    10
2396     5
2397    10
2398    10
2399    10
2400     3
2401    10
2402    10
2403    10
2404     5
2405     2
2406     5
2407    10
2408     5
2409    10
2410     5
2411    10
2412    10
2413    10
2414     5
2415     4
2416    10
2417    10
2418     5
2419    10
2420     8
2421    10
2422     5
2423    10
2424     5
2425     6
2426     5
2427    10
2428     5
2429    10
2430     8
2431    10
2432    10
2433    10
2434    10
2435     8
2436    10
2437    10
2438    10
2439    10
2440    10
2441    10
2442     5
2443    10
2444     5
2445     2
2446     5
2447    10
2448     5
2449    10
2450     7
2451    10
2452    10
2453    10
2454    10
2455    10
2456     5
2457    10
2458    10
2459    10
2460     6
2461    10
2462    10
2463    10
2464     5
2465     2
2466    10
2467    10
2468     5
2469    10
2470     1
2471    10
2472    10
2473    10
2474     5
2475     2
2476    10
2477    10
2478    10
2479    10
2480     3
2481    10
2482     5
2483    10
2484     5
2485     8
2486    10
2487    10
2488    10
2489    10
2490     6
2491    10
2492     5
2493    10
2494    10
2495    10
2496     5
2497    10
2498    10
2499    10
2500     9
2501    10
2502    10
2503    10
2504     5
2505     4
2506     5
2507    10
2508     5
2509    10
2510     5
2511    10
2512     5
2513    10
2514     5
2515    10
2516    10
2517    10
2518    10
2519    10
2520     8
2521    10
2522    10
2523    10
2524     5
2525     4
2526     5
2527    10
2528    10
2529    10
2530     4
2531    10
2532     5
2533    10
2534    10
2535     6
2536    10
2537    10
2538    10
2539    10
2540     3
2541    10
2542     5
2543    10
2544     5
2545    10
2546     5
2547    10
2548     5
2549    10
2550     7
2551    10
2552     5
2553    10
2554     5
2555     8
2556     5
2557    10
2558     5
2559    10
2560    10
2561    10
2562     5
2563    10
2564     5
2565     4
2566    10
2567    10
2568    10
2569    10
2570    10
2571    10
2572    10
2573    10
2574     5
2575    10
2576     5
2577    10
2578    10
2579    10
2580     2
2581    10
2582     5
2583    10
2584    10
2585     6
2586     5
2587    10
2588     5
2589    10
2590     7
2591    10
2592     5
2593    10
2594    10
2595     8
2596     5
2597    10
2598     5
2599    10
2600    10
2601    10
2602     5
2603    10
2604     5
2605    10
2606     5
2607    10
2608     5
2609    10
2610    10
2611    10
2612    10
2613    10
2614     5
2615     6
2616     5
2617    10
2618    10
2619    10
2620     5
2621    10
2622     5
2623    10
2624    10
2625     6
2626    10
2627    10
2628     5
2629    10
2630     4
2631    10
2632    10
2633    10
2634    10
2635     2
2636    10
2637    10
2638     5
2639    10
2640     1
2641    10
2642     5
2643    10
2644     5
2645     4
2646    10
2647    10
2648    10
2649    10
2650     2
2651    10
2652    10
2653    10
2654    10
2655    10
2656     5
2657    10
2658    10
2659    10
2660     1
2661    10
2662     5
2663    10
2664    10
2665     2
2666    10
2667    10
2668     5
2669    10
2670     8
2671    10
2672     5
2673    10
2674    10
2675     2
2676    10
2677    10
2678    10
2679    10
2680     3
2681    10
2682    10
2683    10
2684     5
2685     2
2686    10
2687    10
2688    10
2689    10
2690     3
2691    10
2692    10
2693    10
2694     5
2695     2
2696     5
2697    10
2698    10
2699    10
2700     6
2701    10
2702     5
2703    10
2704     5
2705     2
2706     5
2707    10
2708    10
2709    10
2710     5
2711    10
2712    10
2713    10
2714    10
2715     8
2716     5
2717    10
2718    10
2719    10
2720     3
2721    10
2722     5
2723    10
2724    10
2725     2
2726    10
2727    10
2728    10
2729    10
2730     9
2731    10
2732    10
2733    10
2734    10
2735     2
2736     5
2737    10
2738     5
2739    10
2740     6
2741    10
2742    10
2743    10
2744    10
2745     2
2746     5
2747    10
2748    10
2749    10
2750     4
2751    10
2752     5
2753    10
2754     5
2755     4
2756    10
2757    10
2758    10
2759    10
2760     9
2761    10
2762     5
2763    10
2764     5
2765     8
2766    10
2767    10
2768     5
2769    10
2770     8
2771    10
2772     5
2773    10
2774     5
2775     8
2776     5
2777    10
2778    10
2779    10
2780     7
2781    10
2782     5
2783    10
2784     5
2785     4
2786    10
2787    10
2788    10
2789    10
2790     3
2791    10
2792     5
2793    10
2794    10
2795     4
2796     5
2797    10
2798     5
2799    10
2800     7
2801    10
2802     5
2803    10
2804    10
2805     6
2806     5
2807    10
2808     5
2809    10
2810     1
2811    10
2812     5
2813    10
2814     5
2815     6
2816    10
2817    10
2818    10
2819    10
2820     6
2821    10
2822     5
2823    10
2824    10
2825     8
2826     5
2827    10
2828     5
2829    10
2830     2
2831    10
2832    10
2833    10
2834    10
2835     8
2836    10
2837    10
2838     5
2839    10
2840    10
2841    10
2842    10
2843    10
2844    10
2845     6
2846     5
2847    10
2848     5
2849    10
2850     7
2851    10
2852     5
2853    10
2854    10
2855     4
2856     5
2857    10
2858     5
2859    10
2860     4
2861    10
2862    10
2863    10
2864     5
2865     8
2866    10
2867    10
2868     5
2869    10
2870     3
2871    10
2872    10
2873    10
2874     5
2875     8
2876     5
2877    10
2878     5
2879    10
2880     6
2881    10
2882     5
2883    10
2884    10
2885    10
2886     5
2887    10
2888     5
2889    10
2890     4
2891    10
2892    10
2893    10
2894     5
2895     8
2896    10
2897    10
2898     5
2899    10
2900     2
2901    10
2902    10
2903    10
2904     5
2905    10
2906    10
2907    10
2908     5
2909    10
2910     8
2911    10
2912     5
2913    10
2914    10
2915     2
2916    10
2917    10
2918    10
2919    10
2920     6
2921    10
2922    10
2923    10
2924    10
2925    10
2926     5
2927    10
2928    10
2929    10
2930     6
2931    10
2932    10
2933    10
2934    10
2935     4
2936    10
2937    10
2938    10
2939    10
2940     9
2941    10
2942    10
2943    10
2944     5
2945     8
2946     5
2947    10
2948     5
2949    10
2950     4
2951    10
2952    10
2953    10
2954     5
2955     8
2956    10
2957    10
2958     5
2959    10
2960     8
2961    10
2962     5
2963    10
2964    10
2965     4
2966     5
2967    10
2968     5
2969    10
2970     8
2971    10
2972     5
2973    10
2974    10
2975     6
2976    10
2977    10
2978     5
2979    10
2980     9
2981    10
2982     5
2983    10
2984     5
2985    10
2986    10
2987    10
2988    10
2989    10
2990     9
2991    10
2992    10
2993    10
2994     5
2995    10
2996     5
2997    10
2998    10
2999    10
3000     5