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