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