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