1000 1000000
279 462 61 782 380 27 969 15 407 724 509 976 207 517 602 222 708 107 489 135 193 810 733 230 662 21 70 857 540 257 616 188 208 387 255 309 989 196 243 472 918 564 486 553 126 80 652 49 76 438 312 678 753 187 289 988 464 283 15 933 362 144 722 175 656 615 396 513 240 355 19 601 622 473 877 224 419 444 665 79 829 474 617 579 339 883 371 477 29 915 827 827 703 897 868 710 775 427 98 616 938 284 527 554 949 428 596 773 681 575 127 367 463 526 711 902 107 854 38 778 339 37 887 265 817 102 304 674 712 962 907 7 655 374 938 855 524 203 171 459 115 792 37 674 820 92 142 87 826 560 616 426 729 531 577 620 509 91 436 368 461 219 536 765 732 437 526 26 383 509 432 80 470 936 776 909 868 630 909 460 441 781 75 616 676 47 620 958 399 622 190 56 73 792 618 971 122 889 215 477 806 640 262 779 295 877 253 56 304 488 335 663 248 848 260 550 874 259 62 458 440 202 764 80 278 216 554 741 565 413 684 384 69 494 535 667 598 810 26 734 317 350 765 236 219 714 564 932 489 479 533 999 700 427 79 524 182 148 381 40 959 486 209 804 363 987 806 908 779 489 810 299 251 812 368 597 185 686 495 170 83 971 771 337 300 35 906 234 509 48 383 96 336 820 445 736 672 914 974 239 798 630 638 598 124 142 704 868 449 738 182 898 62 311 577 238 422 381 630 902 89 91 491 636 133 330 551 302 468 376 669 772 789 898 217 147 714 598 702 191 555 265 995 759 865 887 170 34 979 974 188 288 460 330 71 79 92 922 435 569 627 35 879 973 812 150 152 543 115 582 972 626 556 380 130 842 997 35 12 987 595 466 404 729 69 44 630 306 752 519 733 335 118 918 361 439 497 706 249 966 212 321 949 126 966 616 287 151 672 647 84 224 587 288 353 512 275 510 563 590 494 528 180 609 810 671 169 975 602 900 525 19 592 623 928 574 289 519 264 805 396 497 159 287 398 464 93 124 139 6 249 709 454 517 707 549 18 511 399 706 146 983 657 404 958 23 692 389 56 246 380 964 25 390 662 987 120 304 511 47 60 234 415 565 182 87 755 930 107 380 59 988 322 647 670 258 513 43 74 362 720 792 476 512 384 731 351 963 667 465 38 728 516 384 504 911 33 159 150 649 666 630 418 132 969 850 631 642 343 363 631 341 14 356 380 303 986 567 880 790 134 432 279 378 115 329 609 149 558 789 38 571 104 731 740 549 658 689 928 724 765 273 532 798 348 464 157 89 273 342 68 242 132 897 50 390 108 919 452 439 466 472 31 555 553 562 746 55 375 176 273 57 119 964 760 120 147 995 661 335 193 265 227 711 218 56 696 456 5 436 849 639 95 727 269 195 166 333 696 522 347 62 263 549 885 867 132 957 97 63 184 166 722 434 684 809 176 48 549 504 549 194 123 396 704 820 698 36 20 612 270 235 666 633 549 997 480 303 644 906 338 200 616 18 967 596 867 580 630 910 630 64 379 278 10 542 507 829 257 894 604 978 62 386 200 328 989 564 690 722 280 338 883 23 738 204 537 885 245 194 882 814 983 796 565 99 990 22 404 651 561 351 92 571 621 153 581 661 97 698 746 78 288 476 764 323 120 859 868 52 354 763 775 707 931 9 720 225 700 851 863 726 879 129 698 228 17 851 635 610 835 313 158 602 328 87 726 682 171 594 459 71 860 831 4 394 894 440 103 801 214 988 934 438 735 603 633 626 61 239 607 289 447 883 40 40 615 374 373 583 297 60 283 113 587 904 784 892 840 893 735 737 126 301 509 667 274 866 77 961 7 305 408 483 80 629 867 741 908 546 269 178 750 12 860 238 707 334 133 439 112 815 241 204 945 488 49 275 617 374 321 918 251 626 946 676 358 7 243 146 210 231 911 759 835 107 329 164 359 730 426 262 446 301 488 524 528 209 10 301 236 436 274 662 805 275 376 202 584 375 368 524 653 521 400 234 875 241 286 72 494 797 420 479 959 239 300 778 797 125 22 454 865 353 666 949 876 499 269 374 224 292 771 820 323 453 480 220 767 174 261 663 321 624 499 252 759 448 808 782 278 529 952 837 607 559 503 862 188 751 572 42 796 878 149 450 969 314 891 881 277 650 657 827 60 805 674 128 586 827 70 758 715 828 558 151 994 615 788 444 832 881 967 796 734 327 158 441 525 393 791 296 655 470 235 995 985 800 709 252 148 216 672 77 260 159 628 866 215 672
386044 860854 560698 243124 600713 763507 60188 354648 48078 812411 691465 742671 181884 511805 900658 530923 235812 220013 106663 27897 136180 859926 739171 990594 465315 323542 33210 713641 588661 682382 328474 885394 662093 892187 808097 470009 684647 654682 335585 610473 461193 742992 497217 505434 417787 229669 333661 726293 226273 216128 50646 130044 265469 873253 823068 311949 226561 873056 145030 559861 365092 952071 958667 162878 594746 120538 824492 620622 526077 165778 345936 117208 220414 592461 545450 902868 997725 464041 599910 162295 469745 380784 265814 996890 955052 224679 380859 591939 911977 127925 318533 925804 148109 717866 840714 789217 9353 402351 960809 849808 227012 651045 53863 74587 400809 318993 339693 266093 103916 509727 570250 883020 560925 497114 891210 297286 701005 462042 751289 751242 453234 582218 709632 279858 221096 725157 368466 79061 469485 293160 415970 362029 286724 435666 616571 437971 652469 217064 271106 11978 161022 53865 350889 691453 54350 661888 836623 818375 555702 885467 906954 386738 949794 254696 161794 515322 976540 346408 53447 769388 15177 645874 905255 788667 243845 841324 437343 298871 59574 441912 824881 972518 32622 955492 451265 478751 65538 505237 878681 45371 125650 389453 142407 187752 509617 921056 32749 55981 421080 261891 580506 447898 199257 102426 673698 333816 875742 989567 890241 54213 383773 908460 432519 307161 425384 420419 368408 496640 230321 788307 899879 837571 556356 90574 941736 29394 977619 801776 854356 77634 93663 766489 447339 199688 315818 55901 952397 543069 495393 744647 510618 869730 255238 246070 369796 450351 479996 625521 997724 552252 997802 43269 224148 626070 337699 515612 458960 230604 631377 450731 957720 421523 235084 710549 693577 608767 523699 993494 174613 181644 380469 1848 294348 785692 451441 874791 124643 958040 11713 312241 300884 254515 146668 380956 544948 299894 789038 647736 909597 431904 243854 300397 498070 757134 331015 285335 154183 740459 239784 388796 748113 604494 294391 7585 760163 164612 431654 179833 458121 37139 811368 736945 326880 27526 883323 436961 972739 771294 323320 215392 314476 549374 657193 417896 371389 996574 587560 270197 920468 470030 928368 265648 158893 60837 710263 817269 272890 214312 386575 605529 161053 384801 955269 980061 288183 465019 242393 400486 641136 462324 764327 424714 734177 828569 468897 869772 703661 265826 301377 379180 466379 578815 323778 141495 596045 531269 543604 321787 391781 204413 313027 767614 427546 881569 302357 498061 815895 39131 535272 381537 174061 558661 920498 264474 204341 974106 40376 317104 468023 148050 40931 40011 954211 83983 214255 516029 282883 388393 1545 827993 95449 824571 295893 940561 852646 292736 554687 958703 733305 550498 92598 192817 188593 798157 143700 573511 894246 90564 227099 770408 834242 702117 479907 393236 23607 989676 611336 873786 895214 353392 443 444777 268124 627431 982875 292767 473056 938542 757677 218548 15407 744504 358658 464558 581920 397435 846982 431634 858735 901218 250446 731863 764702 180214 435090 234902 721782 799185 202166 169791 601089 210849 181053 257340 851846 190762 808655 631499 673719 351693 409511 626623 132225 478802 426286 590078 552075 877932 587069 55506 844198 690003 75230 632211 500289 8177 654845 985236 171111 488949 705136 631102 520951 936188 670626 625512 443275 746380 248992 180002 495489 301586 233415 178126 975066 295676 901995 119526 797923 42258 40142 475839 618729 627047 143813 366332 381048 75122 267615 703554 913750 86431 924797 62479 280888 469670 297701 211563 275028 247153 753645 472880 391860 169371 281029 606487 505574 863619 732506 907778 796364 972320 872781 605829 365200 592535 77159 459625 728723 81167 203621 569267 387277 400061 503870 760065 91981 955911 498033 420239 532976 946773 948679 260375 712056 895239 436704 90962 61888 662514 356734 810308 141382 770058 554989 58479 75472 413078 772677 958193 590436 960905 195226 988400 496627 852916 674705 381010 473797 895782 282646 794104 780719 669204 501853 673154 609610 485224 565153 110571 296455 922562 82175 803830 940161 550713 995084 102505 831635 861697 995985 642956 457028 276093 321015 764920 174028 264569 622101 295750 147263 421038 75896 366626 454528 144239 183077 284108 943532 332554 535163 712117 281305 554188 490839 706494 42217 810736 145410 243932 602673 287917 908543 546563 575511 149351 923483 41077 488509 895514 546407 907573 878552 876555 890572 297833 224845 223585 182068 237776 684956 91591 859269 283368 169154 332781 939136 311185 244259 353608 632682 337096 221699 674107 667260 210748 382198 512414 201925 145782 117792 361326 187472 136309 101603 734843 91624 859662 173479 410291 379813 895856 667385 398786 834222 852764 940084 218694 770629 126250 463349 487199 119063 627631 310153 487091 194650 145271 728853 846785 19114 726533 32393 263094 678731 85474 56590 256370 301582 153319 527473 221253 2773 33939 148895 656390 820636 949142 304896 411378 328572 644159 597908 28015 519834 433671 919586 544416 869467 607864 791219 456135 614349 971542 631333 601116 816359 390603 451709 273136 272686 782090 823200 286231 888778 243322 7723 555083 160026 324626 458807 472452 46551 824408 213336 6528 866039 193421 818570 810967 374302 803865 697097 137362 552148 293047 468697 571676 83617 265470 444428 519740 347907 851808 712984 404424 654319 999961 668783 66616 957044 26159 215970 87970 639196 75226 431520 447750 548140 705289 236500 917436 762570 12678 926691 59425 927605 166465 975189 707320 664233 697246 438836 153591 272849 250610 772515 204884 117799 281331 33411 524945 93365 596305 396691 176673 961564 557878 802207 795795 161249 547803 890522 397146 605885 129552 177423 456883 296056 857232 851272 184967 751905 78116 609836 854932 23634 870378 850850 191984 782936 5883 29429 229303 929999 628224 894964 135939 906253 248572 436118 50531 278767 454764 624728 449003 59234 7965 65871 658929 552913 480887 245917 802793 833696 531725 842914 888088 416676 74062 383417 849690 979618 593307 576006 9539 272326 290869 550974 719871 590933 638291 364693 365859 773000 781470 686180 983998 15021 246891 5295 76946 218316 859967 239716 269904 970633 544702 6418 522098 727239 571165 58967 568402 327566 347696 617478 540280 629493 999115 704116 678392 133875 564582 420564 55613 748973 835799 245922 321091 83769 418752 526819 401674 355707 943486 481114 661792 160602 935167 297046 482664 997449 709112 865615 901322 384114 351719 150331 543564 957066 600390 832664 62879 252557 638303 575323 188960 154904 22139 409945 451170 73885 99949 305955 656998 112025 403080 772567 997491 482342 34647 96624 40166 431299 845955 840153 862357 551578 183456 411305 505609 20348 348799 380384 144811 243294 424739 893573 541880 980886 723861 906581 994524 870586 62640 227150 512517 57207 967397 830531 238971 598239 915247 426325 129959 790755 100620 72225 321726