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