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