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