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