1 0 2 2 3 3 4 4 5 6 6 8 7 10 8 11 9 12 10 14 11 16 12 18 13 19 14 20 15 22 16 24 17 26 18 27 19 28 20 30 21 32 22 34 23 35 24 36 25 38 26 40 27 42 28 43 29 44 30 46 31 48 32 50 33 51 34 52 35 54 36 56 37 58 38 59 39 60 40 62 41 64 42 66 43 67 44 68 45 70 46 72 47 74 48 75 49 76 50 78 51 80 52 82 53 83 54 84 55 86 56 88 57 90 58 91 59 92 60 94 61 96 62 98 63 99 64 100 65 102 66 104 67 106 68 107 69 108 70 110 71 112 72 114 73 115 74 116 75 118 76 120 77 122 78 123 79 124 80 126 81 128 82 130 83 131 84 132 85 134 86 136 87 138 88 139 89 140 90 142 91 144 92 146 93 147 94 148 95 150 96 152 97 154 98 155 99 156 100 158 101 160 102 162 103 163 104 164 105 166 106 168 107 170 108 171 109 172 110 174 111 176 112 178 113 179 114 180 115 182 116 184 117 186 118 187 119 188 120 190 121 192 122 194 123 195 124 196 125 198 126 200 127 202 128 203 129 204 130 206 131 208 132 210 133 211 134 212 135 214 136 216 137 218 138 219 139 220 140 222 141 224 142 226 143 227 144 228 145 230 146 232 147 234 148 235 149 236 150 238 151 240 152 242 153 243 154 244 155 246 156 248 157 250 158 251 159 252 160 254 161 256 162 258 163 259 164 260 165 262 166 264 167 266 168 267 169 268 170 270 171 272 172 274 173 275 174 276 175 278 176 280 177 282 178 283 179 284 180 286 181 288 182 290 183 291 184 292 185 294 186 296 187 298 188 299 189 300 190 302 191 304 192 306 193 307 194 308 195 310 196 312 197 314 198 315 199 316 200 318 201 320 202 322 203 323 204 324 205 326 206 328 207 330 208 331 209 332 210 334 211 336 212 338 213 339 214 340 215 342 216 344 217 346 218 347 219 348 220 350 221 352 222 354 223 355 224 356 225 358 226 360 227 362 228 363 229 364 230 366 231 368 232 370 233 371 234 372 235 374 236 376 237 378 238 379 239 380 240 382 241 384 242 386 243 387 244 388 245 390 246 392 247 394 248 395 249 396 250 398 251 400 252 402 253 403 254 404 255 406 256 408 257 410 258 411 259 412 260 414 261 416 262 418 263 419 264 420 265 422 266 424 267 426 268 427 269 428 270 430 271 432 272 434 273 435 274 436 275 438 276 440 277 442 278 443 279 444 280 446 281 448 282 450 283 451 284 452 285 454 286 456 287 458 288 459 289 460 290 462 291 464 292 466 293 467 294 468 295 470 296 472 297 474 298 475 299 476 300 478 301 480 302 482 303 483 304 484 305 486 306 488 307 490 308 491 309 492 310 494 311 496 312 498 313 499 314 500 315 502 316 504 317 506 318 507 319 508 320 510 321 512 322 514 323 515 324 516 325 518 326 520 327 522 328 523 329 524 330 526 331 528 332 530 333 531 334 532 335 534 336 536 337 538 338 539 339 540 340 542 341 544 342 546 343 547 344 548 345 550 346 552 347 554 348 555 349 556 350 558 351 560 352 562 353 563 354 564 355 566 356 568 357 570 358 571 359 572 360 574 361 576 362 578 363 579 364 580 365 582 366 584 367 586 368 587 369 588 370 590 371 592 372 594 373 595 374 596 375 598 376 600 377 602 378 603 379 604 380 606 381 608 382 610 383 611 384 612 385 614 386 616 387 618 388 619 389 620 390 622 391 624 392 626 393 627 394 628 395 630 396 632 397 634 398 635 399 636 400 638 401 640 402 642 403 643 404 644 405 646 406 648 407 650 408 651 409 652 410 654 411 656 412 658 413 659 414 660 415 662 416 664 417 666 418 667 419 668 420 670 421 672 422 674 423 675 424 676 425 678 426 680 427 682 428 683 429 684 430 686 431 688 432 690 433 691 434 692 435 694 436 696 437 698 438 699 439 700 440 702 441 704 442 706 443 707 444 708 445 710 446 712 447 714 448 715 449 716 450 718 451 720 452 722 453 723 454 724 455 726 456 728 457 730 458 731 459 732 460 734 461 736 462 738 463 739 464 740 465 742 466 744 467 746 468 747 469 748 470 750 471 752 472 754 473 755 474 756 475 758 476 760 477 762 478 763 479 764 480 766 481 768 482 770 483 771 484 772 485 774 486 776 487 778 488 779 489 780 490 782 491 784 492 786 493 787 494 788 495 790 496 792 497 794 498 795 499 796 500 798 501 800 502 802 503 803 504 804 505 806 506 808 507 810 508 811 509 812 510 814 511 816 512 818 513 819 514 820 515 822 516 824 517 826 518 827 519 828 520 830 521 832 522 834 523 835 524 836 525 838 526 840 527 842 528 843 529 844 530 846 531 848 532 850 533 851 534 852 535 854 536 856 537 858 538 859 539 860 540 862 541 864 542 866 543 867 544 868 545 870 546 872 547 874 548 875 549 876 550 878 551 880 552 882 553 883 554 884 555 886 556 888 557 890 558 891 559 892 560 894 561 896 562 898 563 899 564 900 565 902 566 904 567 906 568 907 569 908 570 910 571 912 572 914 573 915 574 916 575 918 576 920 577 922 578 923 579 924 580 926 581 928 582 930 583 931 584 932 585 934 586 936 587 938 588 939 589 940 590 942 591 944 592 946 593 947 594 948 595 950 596 952 597 954 598 955 599 956 600 958 601 960 602 962 603 963 604 964 605 966 606 968 607 970 608 971 609 972 610 974 611 976 612 978 613 979 614 980 615 982 616 984 617 986 618 987 619 988 620 990 621 992 622 994 623 995 624 996 625 998 626 1000 627 1002 628 1003 629 1004 630 1006 631 1008 632 1010 633 1011 634 1012 635 1014 636 1016 637 1018 638 1019 639 1020 640 1022 641 1024 642 1026 643 1027 644 1028 645 1030 646 1032 647 1034 648 1035 649 1036 650 1038 651 1040 652 1042 653 1043 654 1044 655 1046 656 1048 657 1050 658 1051 659 1052 660 1054 661 1056 662 1058 663 1059 664 1060 665 1062 666 1064 667 1066 668 1067 669 1068 670 1070 671 1072 672 1074 673 1075 674 1076 675 1078 676 1080 677 1082 678 1083 679 1084 680 1086 681 1088 682 1090 683 1091 684 1092 685 1094 686 1096 687 1098 688 1099 689 1100 690 1102 691 1104 692 1106 693 1107 694 1108 695 1110 696 1112 697 1114 698 1115 699 1116 700 1118 701 1120 702 1122 703 1123 704 1124 705 1126 706 1128 707 1130 708 1131 709 1132 710 1134 711 1136 712 1138 713 1139 714 1140 715 1142 716 1144 717 1146 718 1147 719 1148 720 1150 721 1152 722 1154 723 1155 724 1156 725 1158 726 1160 727 1162 728 1163 729 1164 730 1166 731 1168 732 1170 733 1171 734 1172 735 1174 736 1176 737 1178 738 1179 739 1180 740 1182 741 1184 742 1186 743 1187 744 1188 745 1190 746 1192 747 1194 748 1195 749 1196 750 1198 751 1200 752 1202 753 1203 754 1204 755 1206 756 1208 757 1210 758 1211 759 1212 760 1214 761 1216 762 1218 763 1219 764 1220 765 1222 766 1224 767 1226 768 1227 769 1228 770 1230 771 1232 772 1234 773 1235 774 1236 775 1238 776 1240 777 1242 778 1243 779 1244 780 1246 781 1248 782 1250 783 1251 784 1252 785 1254 786 1256 787 1258 788 1259 789 1260 790 1262 791 1264 792 1266 793 1267 794 1268 795 1270 796 1272 797 1274 798 1275 799 1276 800 1278 801 1280 802 1282 803 1283 804 1284 805 1286 806 1288 807 1290 808 1291 809 1292 810 1294 811 1296 812 1298 813 1299 814 1300 815 1302 816 1304 817 1306 818 1307 819 1308 820 1310 821 1312 822 1314 823 1315 824 1316 825 1318 826 1320 827 1322 828 1323 829 1324 830 1326 831 1328 832 1330 833 1331 834 1332 835 1334 836 1336 837 1338 838 1339 839 1340 840 1342 841 1344 842 1346 843 1347 844 1348 845 1350 846 1352 847 1354 848 1355 849 1356 850 1358 851 1360 852 1362 853 1363 854 1364 855 1366 856 1368 857 1370 858 1371 859 1372 860 1374 861 1376 862 1378 863 1379 864 1380 865 1382 866 1384 867 1386 868 1387 869 1388 870 1390 871 1392 872 1394 873 1395 874 1396 875 1398 876 1400 877 1402 878 1403 879 1404 880 1406 881 1408 882 1410 883 1411 884 1412 885 1414 886 1416 887 1418 888 1419 889 1420 890 1422 891 1424 892 1426 893 1427 894 1428 895 1430 896 1432 897 1434 898 1435 899 1436 900 1438 901 1440 902 1442 903 1443 904 1444 905 1446 906 1448 907 1450 908 1451 909 1452 910 1454 911 1456 912 1458 913 1459 914 1460 915 1462 916 1464 917 1466 918 1467 919 1468 920 1470 921 1472 922 1474 923 1475 924 1476 925 1478 926 1480 927 1482 928 1483 929 1484 930 1486 931 1488 932 1490 933 1491 934 1492 935 1494 936 1496 937 1498 938 1499 939 1500 940 1502 941 1504 942 1506 943 1507 944 1508 945 1510 946 1512 947 1514 948 1515 949 1516 950 1518 951 1520 952 1522 953 1523 954 1524 955 1526 956 1528 957 1530 958 1531 959 1532 960 1534 961 1536 962 1538 963 1539 964 1540 965 1542 966 1544 967 1546 968 1547 969 1548 970 1550 971 1552 972 1554 973 1555 974 1556 975 1558 976 1560 977 1562 978 1563 979 1564 980 1566 981 1568 982 1570 983 1571 984 1572 985 1574 986 1576 987 1578 988 1579 989 1580 990 1582 991 1584 992 1586 993 1587 994 1588 995 1590 996 1592 997 1594 998 1595 999 1596 1000 1598