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