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