1 2000 1996 667262 999906 67988 999979 542072 999926 888688 999997 96093 999953 938340 999967 147173 999972 950448 999951 738169 999933 7896 999988 511699 1000000 7151 999981 596306 999917 764140 999903 889441 999982 179274 999993 978628 999980 419108 999943 603974 999923 183658 999910 687832 999939 385002 999921 598782 999916 407633 999997 201245 999944 338971 999977 713928 999969 810063 999932 861731 999919 474099 999904 586782 999996 984668 999970 936903 999950 941903 999901 308647 999984 563260 999924 758189 999947 729410 999951 378413 999990 557038 999943 21036 999930 123128 999962 690820 999982 45164 999915 580299 999941 6959 999906 836813 999911 956820 999937 222410 999927 788623 999907 912489 999924 41067 999980 341833 999961 919926 1000000 659505 999974 837089 999990 401819 999995 918757 999922 645282 999937 44692 999901 750927 999938 309746 999948 771535 999916 608229 999991 582526 999977 362356 999964 258238 999919 12211 999976 947966 999970 229176 999942 789917 999952 16297 999940 485124 999962 948369 999918 427187 999991 574435 999980 354831 999993 106806 999923 702796 999926 203617 999902 210298 999939 974636 999915 721399 999956 597633 999954 604312 999965 554083 999927 954872 999907 136981 999967 33461 999969 316914 999917 123285 999950 913715 999954 261616 999952 121912 999929 823729 999955 673380 999985 224009 999904 736783 999931 382431 999974 571392 999920 56669 999993 589884 999905 261653 1000000 460774 999967 65274 999918 163763 999961 261470 999966 682722 999904 947620 999905 396484 999939 968693 999925 646247 999929 515145 999923 264450 999985 832098 999985 140764 999919 408246 999925 914328 999971 793367 999965 185586 999956 45735 999938 565057 999923 555416 999970 34939 999932 371487 999951 32316 999933 770228 999956 694868 999945 932372 999946 399747 999937 29657 999979 369942 999913 296051 999944 607319 999943 986620 999907 617155 999955 110650 999928 538850 999955 702187 999951 937869 999995 998211 999962 211872 999976 924384 999942 256840 999946 421482 999936 126932 999939 809924 999904 74871 999939 956674 999997 156273 999958 364838 999946 88860 999903 423346 999925 759180 999987 206429 999946 180027 999982 52551 999932 903298 999996 277158 999987 777287 999927 305332 999930 106264 999937 746175 999905 888691 999919 497358 999932 840713 999957 558552 999942 126616 999961 604801 999918 764973 999932 212104 999983 818826 999921 755387 999975 312466 999919 55863 999949 81077 999945 273138 999922 804380 999909 998871 999949 274556 999959 818402 999908 536384 999954 404323 999987 885773 999981 534918 999909 705628 999966 198735 999971 70429 999930 270963 999937 296490 999993 115571 999998 408692 999981 653090 999987 392268 999961 617215 999992 957187 999969 317310 999932 535535 999903 929428 999902 468620 999921 409570 999945 123231 999976 921374 999955 621534 999992 607104 999965 911659 999925 370658 999962 692985 999972 849977 999992 517815 999998 717014 999972 70691 999946 200842 999962 870646 999955 209121 999970 734971 999945 880875 999947 916501 999956 566524 999987 470784 999914 732566 999981 630774 999986 844723 999951 791631 999937 531175 999945 159868 999966 531271 999995 395753 999902 466711 999983 346588 999988 313087 999983 666403 999992 127758 999943 168481 999938 944486 999942 781427 999952 411736 999939 466350 999991 141712 999924 523268 999955 599621 999958 851569 999986 418636 999992 448429 999973 636168 999978 534244 999908 687380 999932 755724 999962 34970 999977 472415 999931 469568 999996 987770 999933 679177 999932 194619 999925 686795 999974 704306 999984 687266 999943 233837 999905 794420 999982 228715 999966 41323 999907 475112 999972 512022 999954 638681 999940 542640 999936 934749 999906 62582 999906 243608 999939 233819 999936 460177 999963 486086 999924 32305 999959 877462 999958 924674 999932 992549 999959 846076 999969 33343 999915 304494 1000000 905519 999993 870786 999959 728377 999919 547687 999977 276052 999917 872798 999937 960754 999926 557083 999988 512665 999929 556677 999994 49358 999956 929986 999925 296151 999989 482704 999936 764991 999936 490808 999915 707667 999906 761168 999967 480447 999945 532624 999928 263605 999954 996611 999952 175088 999982 516370 999949 291375 999993 671239 999936 338001 999909 10909 999911 405718 999928 265931 999938 337388 999933 168089 999925 758830 999972 193707 999913 503684 999905 185572 999936 770659 999952 940791 999926 35431 999902 418010 999974 712448 999919 473875 999992 961764 999954 826726 999931 219261 999968 600647 999946 124410 999948 668128 999904 584691 999916 284704 999967 553037 999926 93847 999911 757401 999998 468149 999986 734330 999966 99827 999989 73443 999929 625749 999925 714140 999994 283249 999928 64040 999928 104999 999982 53030 999998 198868 999932 840604 999970 439661 999991 823617 999971 565723 999986 996296 999919 670134 999945 131708 999999 262266 999961 523559 999947 506740 999915 64134 999923 367744 999957 920111 999954 951663 999973 293065 999997 47007 999905 111142 999986 802162 999911 502917 999910 248119 999981 624486 999928 519980 999952 438634 999958 889661 999942 246443 999908 654967 999986 828037 999909 206694 999949 381581 999951 85169 999930 477980 999978 658680 999951 434791 999997 640042 999947 672450 999952 7744 999984 722328 999962 762556 999931 750449 999995 518557 999933 735763 999962 848768 999902 318575 999957 141582 999970 968580 999989 489573 999905 544672 999935 179269 999926 446997 999922 778261 999965 438075 999998 13255 999933 137085 999951 414058 999990 416058 999994 981348 999935 509072 999979 222987 999939 402676 999980 603064 999919 173478 999938 69474 999994 585237 999945 101048 999924 355288 999913 883977 999945 21966 999915 941300 999918 280619 999983 275470 999909 939617 999928 192192 999991 136117 999958 766262 999910 615191 999979 709651 999934 418658 999920 25575 999934 506565 999975 655407 999971 914271 999931 304601 999982 451884 999956 664011 999901 297716 999920 235049 999992 323176 999966 244659 999988 810788 999948 449865 999949 295035 999951 403162 999951 106249 999948 139880 999961 950132 999963 341883 999968 245889 999951 280378 999981 153416 999959 731077 999987 496070 999907 213112 999991 164423 999969 957318 999960 988935 999997 385196 999947 683315 999982 513501 999972 621509 999937 132764 999969 650060 999980 716295 999987 487198 999943 668182 999990 166755 999930 272698 999928 224051 999989 395891 999926 219465 999920 223764 999961 175582 999999 198669 999905 995724 999998 483245 999944 535184 999994 122170 999991 673773 999924 342051 999997 431421 999985 151834 999987 467789 999979 564597 999942 688598 999955 744423 999929 986659 999994 508015 999947 325867 999941 918316 999984 125605 999998 138087 999996 453049 999937 520379 999973 349460 999945 593307 999976 476215 999909 330283 999957 237376 999965 452931 999924 756128 999947 268095 999905 774681 999974 497409 999996 453503 999956 812910 999952 203027 999922 63729 999992 609129 999936 562094 999973 84696 999977 323990 999952 336771 999982 532029 999930 920024 999999 540003 999981 858509 999939 337438 999974 226571 999988 603852 999977 811807 999911 84369 999959 393946 999970 736216 999957 198863 999941 424904 999903 752627 999919 770627 999983 653899 999917 847103 999958 354840 999948 911196 999959 36082 999913 680307 999997 888690 999971 23654 999950 179303 999938 244826 999999 88015 999957 289224 999963 778909 999973 427902 999994 19713 999959 815841 999945 853369 999922 151651 999966 757793 999955 484645 999929 90628 999943 183012 999959 154725 999981 964980 999977 943655 999976 279223 999960 731902 999907 346908 999980 415071 999954 321942 999983 917290 999978 479163 999914 655461 999988 649244 999943 676576 999906 215128 999925 713717 999930 898855 999983 700500 999959 209551 999971 873482 999992 539941 999922 906518 999926 369093 999945 559363 999941 846975 999906 699394 999989 915725 999965 95084 999984 548418 999951 491734 999940 883969 999961 646415 999963 707879 999945 2044 999953 774367 999913 602710 999994 44629 999938 442579 999910 980070 999952 80953 999940 879368 999931 485705 999952 576511 999999 894260 999913 570141 999914 797098 999910 196854 999904 899297 999990 719471 999915 748643 999933 174212 999937 349398 999969 6873 999954 373718 999930 806046 999905 969160 999966 758389 999956 652562 999972 544167 999953 774081 999988 221218 999950 166087 999979 345767 999961 860101 999957 484674 999957 393361 999991 335256 999978 984025 999944 919354 999906 685657 999945 602002 999928 104058 999908 544401 999952 456937 999962 72602 999954 508220 999922 36437 999993 880291 999977 857340 999915 150162 999998 807445 999941 690060 999901 202913 999904 528585 999951 880742 999909 677494 999993 912543 999985 422634 999971 50376 999998 732919 999964 63080 999922 737939 999932 791384 999940 591474 999985 741675 999971 941826 999971 592221 999916 772715 999999 395108 999936 123963 999997 318523 999907 445451 999932 712083 999973 251154 999948 737889 999960 266198 999927 541069 999937 462753 999954 525868 999938 647461 999939 804748 999963 349947 999997 379245 1000000 917976 999912 705204 999919 484766 999918 531031 999939 95600 999952 265053 999992 134648 999922 764857 999934 422923 999926 116168 999959 840823 999943 289850 999932 463170 999972 695297 999937 180161 999981 588030 999954 152371 999992 691541 999985 725884 999983 721118 999956 759492 999992 483781 999918 526236 999994 457450 999901 306903 999901 619519 999982 667341 999904 812025 999907 177003 999967 741012 999943 66203 999951 766585 999967 711289 999902 95001 999926 803678 999961 334734 999934 57047 999902 71136 999945 181473 999973 918971 999976 741006 999934 279128 999964 8941 999971 547859 999922 625967 999959 553397 999971 124292 999925 234020 999939 803515 999931 693491 999916 747936 999909 357555 999922 554216 999976 775128 999939 821163 999964 626637 999939 110235 999915 679460 999969 540455 999990 107714 999927 960879 999975 525782 999979 783001 999928 35052 999953 851472 999952 23006 999996 1268 999933 947756 999942 904008 999935 335716 999954 267891 999935 157057 999914 665210 999917 432006 999942 822979 999919 822555 999967 857646 999909 519493 999910 367526 999903 323318 999940 301586 999968 261217 999966 383930 999985 771278 999916 182212 999907 194759 999989 871713 999953 810656 999990 420429 999940 745422 999976 290340 999929 38247 999913 173207 999984 970216 999943 924976 999956 224110 999994 538005 999933 846623 999979 995764 999910 402579 999964 822920 999942 525162 999910 867380 999925 41744 999954 393262 999966 202971 999954 930891 999981 250971 999949 862003 999997 371560 999913 857970 999928 200537 999955 479235 999928 150079 999938 468739 999994 572577 999967 791048 999996 67657 999985 27746 999953 719196 999931 810957 999932 349913 999971 455099 999962 151555 999943 80191 999951 516449 999991 954438 999974 735141 999960 214667 999945 566523 999951 779009 999988 805938 999963 906876 999964 718982 999996 713257 999970 678755 999989 49232 999947 459083 999964 620287 999930 223939 999923 594052 999925 424389 999952 837090 999989 175389 999938 965031 999942 621430 999986 154863 999976 965703 999955 900951 999950 245390 999913 106616 999955 642700 999946 862372 999976 184509 999966 106884 999928 172669 999911 467319 999956 623291 999919 737663 999968 104446 999939 982258 999963 855655 999980 557365 999937 24623 999930 412519 999922 277656 999923 964136 999988 718515 999978 577027 999943 114828 999922 738051 999983 545179 999920 765050 999930 129289 999953 51733 999990 938579 999982 609707 999952 701617 999941 10539 999967 626675 999975 140641 999971 94912 1000000 556573 999995 105183 999991 32730 999996 406388 999967 138858 999947 867772 999929 840898 999978 645643 999952 883067 999955 641967 999978 193685 999962 866318 999930 22505 999997 641103 999983 316907 999905 915405 999993 58875 999963 108540 999951 628814 999923 429644 999962 868875 999927 292396 999934 826359 999969 393585 999970 307443 999991 337709 999959 633798 999996 374845 999920 915226 999918 94992 999903 20368 999965 615794 999989 104559 999992 425187 999936 369218 999980 133963 999918 569793 999912 62209 999948 287024 999911 293720 999951 583198 999952 50371 999997 422498 999988 136357 999966 83926 999934 757571 999925 725050 999961 832840 999911 217099 999943 308976 999904 158864 999978 841279 999982 174409 999912 585681 999978 873765 999948 256606 999929 3475 999915 729153 999987 80657 999920 724316 999952 217283 999909 780414 999967 725059 999980 548230 999908 951264 999979 826509 999996 354160 999919 814454 999930 519740 999944 703981 999927 232491 999957 170398 999947 775537 999964 933734 999921 288300 999993 974247 999924 717438 999994 470389 999903 397589 999979 667028 999936 816128 999918 115016 999989 434810 999973 895464 999968 349927 999978 763742 999972 528715 999990 873227 999911 781458 999994 999557 999998 396852 999947 662579 999971 413533 999990 401646 999964 61349 999948 314220 999902 551993 999934 854967 999974 287331 999949 142612 999980 473150 999901 881961 999923 75079 999941 68030 999965 371604 999901 25948 999919 54345 999959 157259 999938 325217 999981 96335 999926 209889 999916 467022 999922 642468 999920 376304 999903 682431 999960 858385 999957 862278 999954 634660 999935 956807 999904 156859 999926 628378 999911 830012 999906 691583 999909 656892 999984 678758 999940 136558 999903 864214 999962 460181 999966 185339 999998 874082 999928 129680 999964 316570 999990 713892 999975 652911 999938 964357 999944 557428 999946 734363 999980 245043 999909 400239 999902 15781 999995 41216 999989 533622 999944 221302 999984 784468 999938 290096 999989 852149 999980 341583 999913 529604 999970 266474 999954 757731 999971 113875 999941 538688 999967 148918 1000000 323526 999925 774699 999950 753524 999978 135123 999903 168680 999982 508218 999935 899682 999940 429259 999959 463555 999948 935262 999982 123837 999901 628708 999954 601602 999993 789044 999997 783053 999930 565759 999903 961660 999976 992173 999912 139210 999987 513228 999973 981386 999936 558255 999931 933402 999989 341418 999994 595173 999923 676066 999941 371934 999974 227746 999976 269175 999946 378331 999929 98917 999928 955153 999994 315922 999923 210439 999928 656240 999903 367761 999994 379963 999984 715776 999939 937688 999903 235733 999932 49919 999968 384738 999906 228003 999956 283973 999930 281729 999915 846866 999941 867199 999904 570486 999996 810464 999912 55132 999955 193451 999903 75928 999975 663816 999934 759112 999938 558367 999915 818071 999940 717717 999929 915739 999917 7074 999909 529709 999996 706641 999921 894830 999920 770206 999927 886682 999932 778539 999946 918063 999937 744535 999909 767897 999921 138641 999906 119635 999956 927303 999997 502990 999914 239839 999908 957052 999992 328813 999970 814932 999941 74814 999927 944278 999954 913870 999996 694319 999986 176324 999920 878379 999959 601114 999983 547479 999908 611541 999996 45757 999915 53473 999915 452916 999927 58232 999968 412957 999908 122626 999935 832740 999992 231617 999931 68729 999985 636237 1000000 661410 999901 693883 999981 282468 999960 899678 999918 801141 999957 822830 999912 826345 999938 824177 999982 3247 999923 35741 999912 871639 999919 888679 999978 462058 999956 922844 999902 514700 999966 499532 999930 116507 999989 100894 999974 533305 999915 140224 999911 171710 999919 578779 999967 144528 999951 4326 999956 474193 999927 387000 999997 948063 999952 840704 999933 424624 999993 399423 999912 456356 999980 947883 999933 285748 999998 252562 999957 617158 999991 565646 999996 345817 999921 818002 999937 600846 999987 69789 999989 590710 999944 832210 999952 316239 999929 747789 999983 867295 999902 810152 999998 86163 999944 243823 999961 752110 999930 368646 999961 661299 999925 9468 999989 971720 999929 172823 999947 822540 999974 651740 999915 779024 999958 971501 999961 101145 999901 772197 999948 808733 999964 6359 999926 149646 999934 476483 999986 60282 999985 141253 999958 463397 999954 351103 999989 68106 999940 833171 999906 797327 999976 443623 999927 973579 999907 473490 999916 331824 999911 36272 999961 174556 999970 911650 999929 621013 999999 861464 999984 534961 999938 827767 999909 601860 999964 532952 999998 305738 999901 736896 999980 859209 999916 331876 999952 677488 999991 955949 999938 998508 999911 618399 999907 701034 999942 680947 999987 834010 999998 9737 999906 965884 999998 572429 999985 86895 999932 591335 999918 53274 999993 531673 999986 156181 999993 278406 999950 358503 999969 531436 999983 254346 999947 125547 999938 500346 999987 339898 999923 67957 999992 423357 999970 554653 999992 603763 999910 243241 999924 449911 999966 958368 999952 578165 999981 441440 999945 446054 999933 302825 999912 512299 999944 417884 999986 812195 999928 888184 999954 201325 999920 833026 999947 314680 999906 400001 999947 674929 999950 8938 999956 864375 999926 973140 999960 156133 999970 210316 999954 85097 999937 998963 999914 803862 999920 468260 999969 153419 999941 457884 999975 434823 999934 656466 999942 250317 999911 913039 999914 248798 999973 399510 999911 976598 999953 287679 999988 257983 999990 481378 999991 401009 999930 292452 999988 740542 999907 424984 999949 45941 999966 29030 1000000 431147 999998 37627 999924 97611 999922 928486 999920 308178 999910 779999 999935 99074 999954 392011 999991 176538 999946 988505 999917 410989 999929 575835 999983 997814 999941 470393 999928 708309 999951 120890 999966 45766 999920 97143 999908 660362 999983 327372 999933 652214 999990 1690 999944 453888 999942 610784 999965 314063 999982 885962 999968 641473 999982 920674 999958 317536 999904 61435 999959 456757 999902 916436 999959 886263 999979 40031 999950 143599 999905 514407 999906 292823 999991 407459 999951 499813 999936 547544 999958 834955 999907 203957 999964 822683 999953 379057 999966 435781 999928 910421 999973 928724 999995 361271 999911 606571 999968 824929 999904 68554 999940 46677 999920 729204 999907 295716 999906 643494 999910 137200 999983 399107 999954 109205 999924 328278 999954 350552 999924 787741 999925 673501 999996 816377 999941 282809 999934 942479 999964 270225 999972 265251 999934 55872 999972 492388 999997 310684 999981 609111 1000000 722512 999911 170601 999954 201078 999970 239759 999955 125645 999995 594166 999936 779945 999923 608106 999948 24648 999977 54564 999982 290082 999978 434341 999948 888517 999975 444828 999953 753215 999990 315780 999973 315477 999918 312601 999971 570187 999981 457975 999945 470516 999905 100477 999985 172541 999935 893535 999965 860300 999994 213269 999952 8141 999975 715191 999988 1715 999983 473888 999976 385604 999908 489047 999927 589199 999945 337567 999974 311100 999959 207739 999985 975664 999996 638350 999988 700238 999915 854862 999982 235478 999929 86775 999967 839988 999904 965950 999977 844130 999963 928461 999999 671890 999961 805530 999940 351220 999953 544370 999960 573805 999998 549582 999955 707754 999983 133564 999966 982618 999942 429014 999967 217817 999932 363971 999942 566515 999921 641068 999948 696030 999924 997677 999953 702864 999924 788337 999931 178399 999988 55850 999934 972573 999984 843490 999907 771018 999929 686397 999955 211386 999995 841011 999904 858447 999987 698892 999946 963879 999906 362588 999932 151362 999930 715178 999953 346861 999912 87648 999937 929332 999957 657484 999968 856171 999961 905770 999904 915116 999957 158956 999997 82827 999929 151446 999927 804018 999942 372000 999993 33600 999916 330691 999951 382508 999978 289614 999955 212976 999905 666985 999921 17051 999926 468657 999912 390779 999965 463011 999959 30996 999964 781429 999992 755936 999927 25622 999969 933216 999957 854139 999918 276503 999978 113105 999906 754095 999956 69254 999981 848481 999989 185249 999977 853023 999940 925721 999917 264600 999948 921849 999975 23031 999951 307845 999980 134743 999952 20755 999956 947840 999955 645356 999919 950179 999933 705541 999931 95682 999954 661751 999992 135187 999995 239039 999901 204084 999916 518795 999927 897443 999958 323543 999928 999822 999995 486135 999928 374667 999918 301887 999942 336924 999918 322747 999998 949083 999987 18827 999968 463275 999926 722102 999915 133679 999924 171027 999952 776409 999999 443612 999908 59677 999991 949963 999936 104115 999991 927603 999955 701547 999914 65485 999931 112919 999989 540138 999944 907245 999959 17377 999951 752014 999978 207974 999905 166667 999904 377562 999985 191342 999966 366354 999957 147352 999932 474626 999907 543011 999917 546775 999981 516959 999986 492162 999992 738625 999929 660016 999988 801911 999916 27800 999913 849941 999949 432864 999902 236315 999938 493403 999911 645544 999983 986153 999966 858438 999932 264204 999963 263502 999981 202559 999902 45852 999911 850119 999946 494561 999908 323894 999926 462271 999982 558710 999919 527984 999994 727350 999954 21670 999955 507459 999933 643170 999929 461940 999912 958128 999969 860565 999990 287763 999951 51927 999928 187953 999910 977099 999981 964192 999921 497634 999983 665266 999916 391535 999910 466145 999984 791988 999929 291798 999949 552886 999943 571153 999942 476399 999934 754530 999922 73340 999961 307124 999992 416209 999983 567911 999904 56893 999941 941190 999925 838236 999952 485540 999944 326566 999986 640609 999993 513515 999942 479870 999983 626113 999949 89192 999975 530127 999979 799189 999956 59169 999944 968153 999987 975734 999957 508111 999951 91876 999987 394750 999976 737982 999975 185512 999980 131768 999915 172429 999981 427545 999929 801812 999930 3765 999946 185214 999998 468065 999955 279335 999901 114409 999957 121918 999985 230748 999964 679587 999902 716829 999916 860623 999956 992152 999996 298160 999934 485568 999907 588817 999913 146170 999902 934672 999981 316837 999976 821883 999956 668274 999930 350156 999915 281654 999920 862981 999930 572885 999909 695662 999996 680931 999998 570174 999912 496951 999993 469473 999905 771115 999930 147014 999902 868611 999970 135061 999964 306809 999961 365216 999983 378870 999945 270520 999919 30161 999910 56662 999901 484458 1000000 593847 999958 720845 999979 554710 999966 807981 999939 89814 999952 610484 999930 585732 999940 883080 999906 850709 999944 560652 999949 606420 999942 774592 999968 591398 999940 623237 999945 262691 999986 605519 999919 544880 999963 533885 999915 484909 999979 694813 999996 882194 999995 322947 999916 241529 999914 145891 999904 322625 1000000 139277 999940 963129 999929 325201 999951 16398 999982 485248 999979 639978 999976 703072 999964 584464 999929 531075 999907 157962 999907 224601 999919 141769 999977 873768 999943 333740 999982 598295 999967 790989 999948 685720 999951 926207 999991 542334 999979 345256 999950 585827 999910 234777 999928 921946 999937 69490 999999 286810 999962 130325 999959 256409 999929 139319 999935 225422 999937 253902 999973 533289 999961 278131 999935 294038 999995 956183 999967 269382 999945 85012 999909 355277 999987 802892 999934 861987 999929 326882 999990 820780 999999 709050 999926 794719 999915 414593 999904 34709 999907 632765 999985 716046 999978 75620 999909 410203 999921 402173 999901 494707 999921 94839 999953 996129 999930 555636 999902 740214 999943 745338 999927 795389 999992 799830 999980 493416 999910 26824 999990 937004 999977 152550 999934 435914 999912 878075 999915 910542 999910 230355 999950 115013 999985 775194 999956 625400 999962 867548 999962 835416 999941 271315 999960 814946 999920 333122 999908 294580 999921 667869 999915 306405 999930 828315 999927 648918 999902 1258 999990 652384 999933 319393 999992 303120 999931 353466 999913 143695 999906 262941 999979 34804 999965 440974 999949 704349 999952 112669 999906 915135 999910 838364 1000000 292507 999961 971006 999985 288093 999933 449949 999990 755223 999956 349068 999952 257081 999954 541515 999981 910172 1000000 512231 999924 891196 999950 228598 999922 494780 999952 850880 999937 769236 999935 788038 999940 370534 999941 499012 999932 305975 999919 138478 999912 116393 999949 305902 999916 375044 999984 542230 999994 632990 999995 593563 999983 9230 999947 370740 999974 295869 999959 777708 999915 320877 999917 240966 999955 441642 999992 38477 999987 160703 999915 490937 999995 795690 999975 909176 999916 484243 999996 375846 999930 46895 999963 366719 999941 1418 999962 916031 999942 413520 999906 362757 999998 721064 999958 506135 999965 824263 999965 270935 999950 874161 999910 555621 999988 31005 999954 213748 999916 651596 999938 70166 999939 718131 999908 243197 999992 830747 999945 68377 999920 732321 999980 212634 999918 188897 999977 915709 999945 55119 999915 470047 999939 766988 999959 212138 999970 136647 999976 373534 999964 167185 999981 437356 999993 880337 999941 489031 999911 696878 999937 659237 999965 902024 999966 17885 999934 14739 999996 335820 999969 822150 999961 110602 999943 935762 999955 622904 999979 966329 999988 166523 999970 10761 999939 495511 999932 533997 999955 727315 999939 341874 999913 121968 999962 830952 999927 619225 999977 679882 999981 520283 999941 894267 999997 991116 999940 147414 999926 279132 999991 883909 999980 531796 999993 45414 999995 278006 999909 377044 999922 110912 999956 43905 999946 569679 999910 390718 999913 318657 999939 479606 999964 673535 999922 148011 999951 212822 999963 80875 999928 99947 999925 531212 999946 198755 999990 239929 999917 843129 999947 888256 999996 324620 999970 215330 999946 516191 999990 582280 999938 74070 999995 557940 999902 674442 999955 779270 999985 605861 999929 320433 999966 692196 999946 280284 999928 529095 999908 454274 999949 116847 999953 135870 999945 674282 999950 382339 999906 977292 999967 503655 999945 589505 999908 215645 999935 944959 999906 819935 1000000 654896 999945 36422 999911 163872 999919 770677 999934 196070 999961 606195 999921 91379 999962 367970 999934 110315 999928 698307 999982 249432 999936 722188 999949 569391 999939 215116 999986 648660 999919 630298 999937 946994 999998 691370 999932 359386 999963 907596 999985 713875 999994 870952 999906 496502 999903 216120 999968 168083 999940 664622 999905 350024 999976 125541 999931 909008 999906 104297 999985 230055 999989 596792 999997 419100 999978 928221 999982 233439 999926 136990 999929 99822 999929 285501 999936 921292 999977 222013 999990 906306 999951 181619 999919 248919 999983 362703 999905 223072 999943 890897 999964 584332 999917 803189 999968 610092 999969 300907 999975 250983 999982 172520 999929 636225 999917 233708 999974 535860 999925 120660 999929 33727 999932 837251 999922 430188 999922 231841 999939 354538 999916 433526 999956 931186 999942 769400 999964 809474 999970 408799 999986 324472 999925 307195 999910 757487 999980 280454 999913 267367 999927 548697 999949 826238 999941 127850 999956 331414 999977 49723 999971 356223 999982 434690 999919 372468 999934 961473 999952 610306 999971 880790 999955 623546 999906 261645 999991 888026 999934 394126 999950 84434 999906 32447 999986 971494 999951 217083 999936 918949 999999 159369 999914 850886 999906 651792 999939 850834 999903 560157 999903 956187 999971 958141 999997 632733 999926 137187 999986 733055 999909 512655 999941 609601 999978 653811 999984 464678 999946 924889 999928 305602 999903 943351 999950 125423 999915 943475 999996 755365 999905 669795 999946 574686 999928 567555 999957 413629 999964 683547 999978 257660 999928 262795 999916 545434 999997 102551 999983 654646 999990 511155 999950 309097 999920 483748 999998 933807 999977 986838 999951 65414 999904 478373 999954 42920 999947 9208 999990 394468 999954 307213 999976 76372 999961 201690 999984 867052 999950 588305 999997 888210 999955 229910 999905 17251 999950 608754 999977 55061 999931 187565 999927 514849 999937 308509 999922 643397 999995 307900 999938 520569 1000000 652100 999988 174848 999910 59 999905