0 1 1 2 2 4 3 3 4 7 5 5 6 9 7 11 8 14 9 8 10 13 11 6 12 17 13 10 14 19 15 12 16 21 17 15 18 23 19 25 20 27 21 29 22 31 23 33 24 38 25 18 26 36 27 43 28 41 29 20 30 35 31 45 32 47 33 22 34 51 35 16 36 53 37 24 38 49 39 26 40 40 41 28 42 50 43 30 44 57 45 32 46 59 47 34 48 55 49 39 50 65 51 61 52 63 53 37 54 67 55 44 56 71 57 42 58 75 59 69 60 77 61 73 62 79 63 46 64 81 65 48 66 85 67 83 68 89 69 52 70 91 71 93 72 95 73 54 74 99 75 87 76 101 77 97 78 103 79 105 80 107 81 109 82 113 83 115 84 119 85 121 86 111 87 127 88 129 89 58 90 133 91 117 92 131 93 60 94 125 95 135 96 139 97 56 98 137 99 123 100 143 101 66 102 147 103 62 104 141 105 64 106 151 107 145 108 149 109 68 110 124 111 155 112 159 113 72 114 163 115 153 116 157 117 76 118 167 119 70 120 161 121 78 122 169 123 74 124 173 125 80 126 165 127 171 128 177 129 82 130 175 131 179 132 183 133 86 134 181 135 84 136 187 137 90 138 191 139 189 140 185 141 92 142 195 143 94 144 199 145 96 146 197 147 193 148 204 149 100 150 206 151 88 152 202 153 102 154 210 155 98 156 216 157 104 158 208 159 106 160 219 161 108 162 214 163 110 164 223 165 114 166 201 167 116 168 225 169 120 170 221 171 122 172 227 173 112 174 229 175 128 176 231 177 130 178 233 179 235 180 237 181 134 182 242 183 118 184 240 185 132 186 246 187 212 188 248 189 126 190 252 191 136 192 254 193 140 194 239 195 244 196 218 197 138 198 258 199 256 200 260 201 144 202 262 203 250 204 266 205 148 206 268 207 264 208 272 209 142 210 274 211 270 212 276 213 152 214 280 215 146 216 282 217 150 218 213 219 278 220 286 221 284 222 288 223 156 224 290 225 160 226 294 227 292 228 298 229 164 230 300 231 154 232 304 233 158 234 306 235 296 236 308 237 168 238 310 239 312 240 314 241 162 242 318 243 320 244 316 245 170 246 322 247 302 248 324 249 174 250 328 251 326 252 330 253 166 254 332 255 172 256 340 257 178 258 336 259 334 260 338 261 176 262 346 263 180 264 350 265 184 266 348 267 344 268 354 269 182 270 356 271 352 272 360 273 188 274 362 275 358 276 366 277 192 278 372 279 190 280 374 281 186 282 370 283 342 284 380 285 196 286 378 287 364 288 382 289 200 290 386 291 376 292 384 293 198 294 390 295 194 296 392 297 205 298 368 299 388 300 398 301 207 302 394 303 396 304 402 305 203 306 404 307 400 308 369 309 211 310 408 311 410 312 406 313 217 314 412 315 414 316 418 317 209 318 416 319 422 320 424 321 220 322 428 323 426 324 432 325 215 326 434 327 420 328 430 329 224 330 440 331 436 332 438 333 442 334 446 335 444 336 450 337 226 338 454 339 448 340 458 341 222 342 460 343 456 344 452 345 228 346 464 347 462 348 466 349 230 350 470 351 468 352 474 353 232 354 478 355 476 356 482 357 234 358 484 359 236 360 472 361 238 362 488 363 486 364 490 365 243 366 492 367 480 368 496 369 241 370 498 371 494 372 506 373 247 374 502 375 500 376 504 377 249 378 510 379 512 380 516 381 253 382 520 383 514 384 524 385 255 386 508 387 518 388 528 389 526 390 534 391 245 392 530 393 522 394 540 395 532 396 544 397 259 398 536 399 257 400 538 401 261 402 550 403 542 404 546 405 263 406 554 407 251 408 556 409 267 410 548 411 552 412 560 413 269 414 566 415 265 416 562 417 273 418 564 419 558 420 570 421 275 422 578 423 271 424 574 425 277 426 582 427 568 428 572 429 281 430 588 431 576 432 584 433 283 434 586 435 580 436 590 437 592 438 594 439 279 440 598 441 287 442 602 443 285 444 606 445 289 446 608 447 596 448 612 449 291 450 614 451 604 452 600 453 295 454 618 455 293 456 620 457 299 458 624 459 616 460 626 461 301 462 622 463 628 464 632 465 305 466 630 467 610 468 636 469 307 470 640 471 297 472 644 473 309 474 646 475 634 476 648 477 311 478 650 479 313 480 652 481 315 482 654 483 656 484 660 485 319 486 658 487 321 488 638 489 317 490 664 491 642 492 668 493 323 494 670 495 303 496 666 497 325 498 674 499 662 500 676 501 329 502 639 503 327 504 684 505 331 506 678 507 680 508 682 509 333 510 686 511 672 512 690 513 341 514 694 515 692 516 688 517 337 518 698 519 335 520 704 521 339 522 700 523 702 524 708 525 347 526 696 527 706 528 712 529 351 530 710 531 714 532 718 533 349 534 716 535 345 536 722 537 355 538 726 539 724 540 730 541 357 542 720 543 353 544 734 545 361 546 736 547 728 548 738 549 363 550 740 551 359 552 744 553 367 554 746 555 742 556 748 557 373 558 752 559 750 560 754 561 375 562 758 563 732 564 762 565 371 566 764 567 760 568 766 569 381 570 768 571 756 572 770 573 379 574 774 575 365 576 776 577 383 578 778 579 772 580 780 581 387 582 782 583 377 584 786 585 385 586 790 587 784 588 794 589 391 590 796 591 792 592 798 593 393 594 802 595 788 596 804 597 800 598 808 599 389 600 810 601 399 602 812 603 806 604 816 605 395 606 818 607 397 608 822 609 403 610 824 611 814 612 830 613 405 614 828 615 401 616 834 617 820 618 836 619 826 620 840 621 409 622 846 623 411 624 838 625 407 626 844 627 832 628 850 629 413 630 842 631 415 632 854 633 419 634 852 635 848 636 858 637 417 638 864 639 423 640 860 641 425 642 868 643 856 644 870 645 429 646 874 647 427 648 876 649 433 650 878 651 862 652 880 653 435 654 886 655 421 656 866 657 431 658 884 659 882 660 890 661 441 662 892 663 437 664 896 665 439 666 900 667 443 668 894 669 447 670 904 671 445 672 906 673 451 674 898 675 872 676 910 677 455 678 908 679 449 680 902 681 459 682 914 683 888 684 918 685 461 686 916 687 457 688 922 689 453 690 924 691 873 692 920 693 465 694 928 695 463 696 926 697 467 698 934 699 912 700 932 701 471 702 936 703 469 704 938 705 475 706 942 707 930 708 944 709 479 710 948 711 477 712 950 713 483 714 952 715 940 716 954 717 485 718 960 719 946 720 958 721 473 722 964 723 956 724 966 725 489 726 970 727 487 728 974 729 491 730 968 731 962 732 978 733 493 734 980 735 481 736 982 737 497 738 986 739 972 740 988 741 499 742 990 743 495 744 994 745 507 746 996 747 984 748 998 749 503 750 1000 751 501 752 1002 753 505 754 1006 755 976 756 1008 757 511 758 1010 759 513 760 1013 761 517 762 1015 763 992 764 1017 765 521 766 1019 767 515 768 1021 769 525 770 1023 771 1004 772 1025 773 509 774 1027 775 519 776 1029 777 529 778 1031 779 527 780 1033 781 535 782 1037 783 1035 784 1039 785 531 786 1043 787 523 788 1047 789 541 790 1049 791 533 792 1053 793 545 794 1055 795 1041 796 1057 797 537 798 1059 799 1012 800 1061 801 539 802 1063 803 1045 804 1065 805 551 806 1067 807 543 808 1071 809 547 810 1073 811 1069 812 1075 813 555 814 1077 815 1051 816 1079 817 557 818 1083 819 1081 820 1085 821 549 822 1089 823 553 824 1093 825 561 826 1095 827 1091 828 1097 829 567 830 1099 831 1087 832 1101 833 563 834 1105 835 1103 836 1107 837 565 838 1109 839 559 840 1113 841 571 842 1117 843 1111 844 1121 845 579 846 1123 847 1119 848 1125 849 575 850 1129 851 1127 852 1131 853 583 854 1135 855 569 856 1139 857 573 858 1141 859 1115 860 1143 861 589 862 1145 863 577 864 1147 865 585 866 1149 867 1137 868 1151 869 587 870 1153 871 581 872 1155 873 591 874 1157 875 593 876 1159 877 595 878 1161 879 1133 880 1165 881 599 882 1169 883 1163 884 1171 885 603 886 1173 887 1175 888 1179 889 607 890 1177 891 1167 892 1183 893 609 894 1185 895 597 896 1193 897 613 898 1189 899 1181 900 1187 901 615 902 1191 903 605 904 1197 905 601 906 1203 907 1199 908 1207 909 619 910 1211 911 1195 912 1215 913 621 914 1205 915 1201 916 1219 917 625 918 1221 919 617 920 1209 921 627 922 1225 923 1213 924 1223 925 623 926 1231 927 629 928 1227 929 633 930 1235 931 1217 932 1237 933 631 934 1229 935 611 936 1241 937 637 938 1251 939 1233 940 1243 941 641 942 1245 943 1239 944 1247 945 645 946 1255 947 1249 948 1257 949 647 950 1261 951 635 952 1265 953 649 954 1269 955 1263 956 1271 957 651 958 1273 959 1253 960 1259 961 653 962 1277 963 1275 964 1279 965 655 966 1281 967 657 968 1285 969 661 970 1287 971 1267 972 1289 973 659 974 1293 975 1283 976 1299 977 1291 978 1301 979 1295 980 1297 981 665 982 1305 983 643 984 1309 985 669 986 1313 987 1307 988 1317 989 671 990 1319 991 1303 992 1311 993 667 994 1323 995 1321 996 1325 997 675 998 1327 999 663 1000 1331