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