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