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