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