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