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