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