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