1 2000 1997 615500 999939 841250 999982 296923 999959 843104 999931 72711 999945 198047 999931 517475 999965 53058 1000000 943460 999910 659345 999930 262540 999948 175491 999919 263704 999923 354515 999908 189930 999917 736169 999969 12732 999958 434569 999935 713667 999934 138391 999915 975150 999987 900314 999902 147856 999938 592037 999995 98966 999964 271897 999921 913822 999977 383153 999996 88881 999905 780071 999971 333502 999959 733897 999926 701467 999909 298351 999969 788296 999906 864060 999933 754147 999901 225914 999905 454883 999922 205179 999939 813253 999941 652972 999997 481091 999903 844571 999942 615491 999924 552860 999975 612650 999967 799055 999948 93167 999954 760216 999972 17767 999932 446358 999921 178558 999958 628807 1000000 192863 999949 104128 999989 864319 999928 937883 999949 986820 999961 521882 999932 219053 999992 564899 999995 449734 999911 527411 999914 372515 999953 56434 999959 605750 999994 462536 999981 456280 999960 347048 999984 349667 999991 920185 999951 696166 999988 481012 999974 939466 999994 187419 999909 236302 999996 720086 999922 117531 999930 559533 999921 127789 999992 620513 999925 709338 999949 419804 999971 349039 999956 701470 999928 515707 999974 970511 999967 968328 999917 293060 999970 859989 999912 640735 999977 437066 999993 704778 999981 98674 999936 379408 999936 143441 999911 804631 999988 681556 999957 554120 999940 712516 999958 184439 999982 590769 999940 540698 999961 964606 999985 912340 999921 201708 999910 842033 999959 94101 999915 318410 999912 996334 999930 454801 999986 251935 999914 764479 999906 208991 999909 658665 999969 77180 999910 196043 999956 173892 1000000 290408 999909 997187 999965 865787 999927 940305 999921 482691 1000000 352221 999914 937541 999976 44929 999995 736059 999965 876476 999921 560803 999977 908405 999993 51682 999910 46462 999940 673387 999977 533168 999987 243356 999923 308810 999934 17952 999919 104204 999942 400642 999939 965538 999997 832611 1000000 609557 999967 417467 999921 610167 999984 80902 999956 101167 999930 75619 999993 972015 999997 728985 999921 822281 999918 854844 999973 207520 999906 513761 999970 304017 999907 727888 999982 672851 999936 362826 999997 675647 999928 479383 999977 340633 999949 912182 999987 968011 999912 419236 999905 308096 999928 462296 999964 740233 999915 957068 999906 991124 999932 760532 999948 614215 999937 46829 999995 849756 999967 55249 999916 433483 999992 390753 999962 242128 999902 135440 999904 854595 999984 278245 999925 119099 999960 373729 999909 857927 999909 888184 999969 761442 999929 64301 999925 180851 999948 126304 999909 964834 999931 498946 999935 558673 999902 372405 999971 427656 999912 866316 999960 939650 999985 302938 999991 194115 999957 444466 999981 912960 999919 610193 999920 840232 999989 55341 999923 826691 999973 330859 999935 699848 999917 617208 999942 725801 999925 354069 999910 579968 999964 293412 999901 300023 999991 65147 999938 794685 999920 943360 999955 547085 999905 942956 999969 45030 999990 135553 999901 712233 999958 827267 999913 297002 999945 236773 999961 852334 999910 357958 999914 548015 999973 669328 999964 520278 999970 46043 999945 180769 999967 893833 999985 891262 999967 953570 999974 195709 999993 155463 999904 70517 999963 24350 999954 523942 999992 143468 999974 603665 999946 330972 999974 424135 999943 860361 999915 185180 999959 68523 999930 706001 999932 205572 999989 616001 999933 409477 999926 7361 999927 610899 999987 636474 999913 917361 999928 836218 999961 69352 999961 565615 999963 982524 999920 994780 999943 95194 999937 553252 999951 983848 999975 290930 999904 5177 999996 66814 999905 806558 999902 739771 999969 779264 999970 384854 999972 257989 999962 514070 999925 610991 999991 812043 999974 884181 999945 264449 999915 863214 999911 201149 999976 270666 999988 499984 999963 551643 999919 389974 999960 205951 999972 833828 999960 50436 999980 866265 999927 670231 999937 380414 999967 499744 999964 621246 999943 673582 999909 997991 999981 283842 999963 173887 999971 662114 999948 703132 999930 806683 999920 888645 999917 444845 999924 163314 999993 664735 999987 181800 999910 806990 999920 36165 999960 500827 999984 553014 999957 866129 999957 531766 999921 231691 999967 755309 999980 564590 999973 48641 999952 461592 999911 687874 999916 861173 1000000 578726 999911 166467 999959 918221 999943 381013 999966 344877 999952 154907 999990 966358 999972 296589 999934 470137 999987 269737 999901 672961 999959 402421 999921 156554 999952 573538 999976 455346 999936 568087 999912 662139 999941 802690 999925 907667 999918 645876 999959 817550 999968 439580 999910 183201 999981 690263 999983 52817 999969 85055 999998 131893 999918 992124 999986 622012 999932 960349 1000000 374086 999964 372944 999938 712572 999980 913198 999968 95789 999969 488898 999936 925625 999911 201240 999930 298218 999923 626751 999974 819950 999930 150376 999932 918162 999986 85783 999985 13005 999948 828693 999971 599952 999996 177580 999910 929949 999990 48140 999920 696245 999997 466826 999932 466592 999912 663882 999992 297019 999959 321248 999906 610780 999973 770555 999994 217159 999966 758980 999919 744779 999991 596404 999978 301687 999932 124231 999917 95361 999920 790040 999927 998387 999905 411910 999929 944865 999926 681755 999933 887427 999940 719697 999976 81156 999943 796541 999946 74967 999985 385377 999950 467544 999966 282256 999976 47420 999986 606616 999902 343291 999939 923789 999949 652095 999903 425093 999907 251188 999919 329362 999952 821040 999921 265261 999952 187179 999919 599418 999920 434259 999969 397808 999924 170233 999956 139681 999974 598812 999931 895098 999922 189974 999987 613081 999977 302328 999917 66036 999950 62135 999948 824240 999963 371696 999911 220457 999953 875228 999964 923463 999941 814654 999991 744714 999960 141975 999962 850421 999936 778786 999961 493423 999919 842270 999935 705165 999964 878838 999972 692458 999972 713572 999945 706114 999919 647495 999981 637576 999918 972869 999956 434112 999902 814216 999914 472550 999996 800045 999953 897283 999948 365468 999944 585254 999925 124086 999936 525406 999937 314482 999948 851494 999988 926404 999938 511492 999984 313082 999919 108596 999976 277305 999948 80119 999961 542621 999935 492667 999940 103817 999944 877250 999910 142599 999960 115610 999925 533842 999944 630543 999942 881396 999994 302845 999979 882940 999907 913669 999958 397337 999945 599229 999963 267062 999985 676269 999942 476121 999914 204826 999972 533410 999930 789719 999911 324312 999926 560119 999948 967517 999936 382335 999911 825293 999986 753417 999911 444290 999994 271737 999986 523104 999999 809724 999993 894917 999999 264808 999928 415803 999999 423889 999915 591256 999913 805228 999974 84577 999984 578335 999952 863923 999955 915807 999966 255843 999924 231857 999986 226537 999979 419769 999984 187640 999961 258861 999957 739699 999992 897896 999927 136859 999959 536867 999901 748545 999984 184541 999922 315103 999952 939477 999970 580060 999998 920296 999938 186592 999989 507279 999961 404939 999905 266389 999960 312642 999963 615255 999947 413820 999955 262517 999913 359329 999942 625563 999918 8975 999933 675157 999990 945075 999981 198877 1000000 693885 999939 545583 999923 538940 999933 731542 999963 29777 999979 152281 999988 351812 999942 879123 999970 619224 999906 891444 999934 787033 999997 826319 999956 708186 999992 132447 999913 472380 999942 85549 999987 208826 999987 126962 999968 298964 999901 991990 999958 286280 999994 887890 999946 846607 999907 277757 999909 458123 999912 369947 999918 475887 999999 731840 999926 244098 999974 614827 999952 700316 999960 328445 999944 551055 999983 37837 999938 346451 999943 316320 999921 404542 999903 288971 999922 471833 999905 875196 999923 568601 999951 75737 999946 378805 999916 920218 999933 38866 999940 472313 999905 436586 999917 215282 999992 87015 999973 594386 999976 104968 999991 726464 999960 290534 999982 884079 999944 289760 999948 633920 999981 101591 999967 493944 999968 831653 999906 795288 999914 115518 999913 377599 999946 246059 999997 629597 999908 265259 999912 194289 999960 363509 999938 740266 999928 476795 999929 315308 999964 96054 999963 28874 1000000 742231 999953 898408 999926 829987 999923 950107 999913 734909 999975 791610 999946 296035 999944 546835 999969 949818 999963 468250 999994 426517 999945 887783 999906 338973 999956 79427 999923 580314 999932 510264 999989 642771 999947 34726 999974 685491 999956 739827 999945 802297 999949 218534 999961 229695 999997 943580 999938 20273 999914 859524 999973 561877 999976 386505 999988 883557 999996 259818 999990 983623 999916 391852 999906 530620 999930 108125 999907 834646 999967 306558 999949 200490 999968 444363 999952 602748 999934 386646 999905 437146 999940 543877 999961 395895 999979 457981 999978 364437 999977 742732 999979 3727 999956 770584 999915 899975 999947 344703 999957 311568 999987 662632 999992 67136 999947 145321 999985 251638 999907 273210 999991 617717 999953 853955 999974 274080 999921 478828 999976 351946 999945 274515 999942 40350 999980 445047 999928 972995 999995 703303 999957 534153 999929 324018 999926 951795 999968 950161 999922 886462 999939 284002 999917 336962 999938 889681 999903 990048 999903 231432 999983 884162 999995 825706 999924 102439 999905 519559 999958 905960 999908 251048 999946 497310 999957 142895 999921 387903 999953 285690 999912 796160 999946 732130 999967 33574 999983 230730 999944 585138 999959 150528 999936 44716 999938 535483 1000000 368465 999940 621867 999913 66003 999977 847694 999968 576314 999950 450601 999994 692748 999969 293234 999999 12147 999905 515497 999956 138620 999951 43196 999918 308087 999953 859558 999909 802344 999903 535594 999934 444075 999953 822108 999960 614238 999997 417279 999979 924466 999945 984673 999928 631200 999962 672496 999984 294789 999969 291646 999933 402393 999966 933360 999972 700617 999997 604752 999912 956878 999974 867450 999959 483702 999988 664128 999931 843411 999923 624905 999944 210973 999999 22395 999961 449849 999903 681137 999947 466001 999992 925501 999920 186523 999907 525999 999930 202175 999977 875781 999930 666698 999978 407726 999963 781629 999941 545421 999987 176023 999968 266702 999946 600767 999944 647026 999944 236229 999981 37870 999914 821661 999961 243194 999927 292098 999929 263311 999964 681359 999959 508680 999933 269474 999989 235687 999946 239047 999995 943364 999952 133836 999981 104108 999979 794919 999918 130701 999940 312948 999921 19980 999943 179829 999962 275780 999926 137536 999955 520200 999938 873299 999926 601137 999943 450972 999915 905054 999994 915081 999914 730377 999989 472711 999970 683923 999963 497461 999901 321436 999949 326874 999920 479167 999937 265501 999959 549069 999950 762120 999911 878590 999948 198822 999929 42615 999951 917933 999972 317180 999943 53759 999942 788492 999971 449147 999999 31667 999953 425071 999959 510394 999936 623281 999934 975716 999966 609148 999990 488444 999929 590155 999931 73930 999903 144130 999982 969122 999997 492945 999976 398261 999929 868533 999936 652668 999908 459453 999982 610610 999916 425723 999921 757496 999997 237977 999988 805961 999956 199651 999928 128688 999997 188974 999997 246772 999927 174328 999980 787090 999911 778631 999929 952597 999949 240082 999923 579488 999955 356146 1000000 231313 999902 35800 999919 237612 999992 980812 999993 614306 999955 51333 999954 250538 999990 374733 999970 103585 999971 203606 999974 923663 999927 672629 999941 517458 999924 525725 999997 737393 999999 83145 999953 356043 999946 650242 999956 752007 999948 291628 999931 453043 1000000 277545 999927 942157 999949 942781 999967 263420 999922 976264 999998 836774 999998 948895 999999 643107 999984 997772 999963 184519 999990 811021 999933 601949 999963 966087 999907 750653 999994 244691 999993 359134 999942 114794 999971 651846 999926 745684 999966 453976 999946 959582 999945 109859 999993 623070 999912 751627 999962 607301 999949 794359 999951 612833 999915 187678 999931 426590 999942 715028 999963 407018 999999 929105 999926 591467 999937 307333 999990 442773 999914 63477 999943 326204 999949 180450 999977 418169 999902 704124 999987 960764 999938 949589 999934 764972 999996 144664 999990 550368 999968 105139 999995 95902 999958 591851 999923 266846 999938 671300 999936 801080 999935 350485 999965 93682 999937 316241 999910 429465 999919 151999 999968 940954 999983 472254 999922 874207 999976 612737 999946 290302 999944 222082 999901 263705 999915 656288 999986 862249 999907 534431 999933 64048 999991 439402 999956 398312 999972 614009 999991 67519 999950 536695 999908 551407 999923 349351 999993 331067 999919 970355 999964 700991 999945 70745 999995 211469 999953 726305 999965 366670 999987 620664 999986 721101 999979 875135 999920 381904 999957 276376 999909 527070 999971 484144 999919 814739 999924 390584 999922 508131 999984 51572 999970 287489 999955 400643 999998 548841 999910 232770 999926 197213 999941 911929 999904 134727 999955 130836 999960 15878 999967 32237 999941 205024 999984 647635 999929 841876 999929 995245 999908 422149 999918 74370 999967 364449 999964 244930 999965 774535 999990 168537 999926 234297 999913 228469 999989 916393 999976 761118 999956 133872 999932 673819 999967 804474 999996 657198 999925 786696 999915 231203 999910 818347 999994 91642 999914 290389 999911 790846 999944 56135 999936 835845 999923 114485 999943 342137 999987 906767 999951 304183 999973 378228 999928 245052 999965 702371 999974 335520 999980 904343 999972 115980 999985 415404 999908 900184 999962 999515 999959 646548 999995 589715 999983 708347 999970 784736 999931 324336 999973 559298 999919 967344 999936 480719 999928 430343 999963 938484 999973 666298 999942 912913 999958 202853 999951 264906 999988 228778 999908 171921 999991 725234 999919 481470 999903 815957 999945 182003 999937 333035 999933 318761 999909 260071 999914 708424 999933 123913 999926 24388 999953 239718 999973 606001 999940 560483 999972 144993 999935 800902 999975 332449 999957 710597 999944 715620 999923 336913 999999 388016 999901 96544 999915 213902 999928 374661 999932 420191 999937 181073 999983 31184 999958 370379 999925 861749 999992 816470 999965 276852 999954 70027 999975 157978 999953 51683 999992 142852 999968 94104 1000000 188325 999942 672866 999991 705994 999977 887721 999951 829801 999951 22963 999908 299208 999931 306717 999938 372288 999996 991166 999939 112710 999969 773394 999994 455254 999904 948997 999936 975366 999961 983479 999903 607227 999991 113064 999982 708518 999939 635272 999923 243667 999959 603049 999917 206578 999967 983500 999961 416405 999947 60129 999942 603650 999909 130144 999914 206336 999999 384399 999909 12215 999947 50108 999995 127575 999913 777519 999988 748223 999958 993075 999981 131388 999954 997938 999911 71919 999936 765443 999933 27226 999994 902328 999931 824892 999971 896784 999915 171616 999913 865607 999978 984328 999909 737046 999995 184637 999902 304375 999999 350176 999925 712272 999940 825216 999962 716253 999941 439607 999904 790599 999961 413536 999929 432187 999914 454333 999972 867811 999924 244 999963 197139 999965 182635 999964 212578 999975 61820 999996 453928 999945 287820 999975 552493 999946 92878 999982 98729 999927 449177 999987 71752 999962 968621 999939 793892 999962 909088 999929 219054 999906 566645 999902 247043 999960 946186 999995 826175 999918 978384 999971 640505 999938 729412 999916 647612 999912 852622 999951 745823 999917 296535 999980 369928 999916 107744 999951 969858 999964 537423 999937 77667 999968 168721 999920 47784 999943 65956 999904 708635 999929 103291 999945 442292 999926 624758 999920 447016 999963 933641 999937 563976 999982 133086 999963 591056 999935 639590 999964 736012 999982 740780 999965 101288 999970 179212 999962 20884 999952 191 999931 234420 999933 903684 999962 709632 999913 49623 999925 521093 999973 664945 999962 362126 999911 483285 999918 23702 999919 127775 999909 165178 999974 988719 999952 625808 999993 689928 999927 309167 999972 950835 999991 893439 999904 532842 999942 860773 999993 452679 999979 435614 999925 434156 999976 71405 999960 323149 999927 933574 999937 415682 999930 38122 1000000 468556 999969 875622 999901 606404 999943 423611 999973 187347 999941 890204 999982 975661 999983 836948 999929 679645 999917 653718 999970 811477 999904 146272 999943 230192 999998 381395 999959 547807 999930 854367 999956 303460 999911 205002 999923 699127 999940 354802 999946 383065 999965 488464 999978 209535 999959 655767 999931 905057 999987 909609 999991 629758 999941 408233 999950 615861 999999 4066 999978 518244 999957 52064 999975 958778 999908 730084 999963 216406 999936 846235 999991 872050 999929 36271 999977 268634 999977 706013 999952 917220 999962 729023 999997 797731 999933 990720 999921 680574 999945 508838 999982 174975 999990 746066 999976 284395 999930 562853 999919 625596 999957 880377 999964 365670 999939 501615 999917 432670 999901 423510 999959 517383 999996 624243 999977 727323 999923 890617 999901 590463 999903 476649 999963 338943 999932 286479 999936 606586 999948 85010 999955 865276 999962 119264 999961 394909 999905 551261 999948 303435 999931 403127 999965 790341 999932 494208 999996 418205 999924 367813 999908 873400 999962 781416 999919 888070 999950 993598 999982 55474 999944 570246 999964 852792 1000000 411510 999957 227764 999918 415979 999963 596690 999906 796025 999903 261853 999991 963524 999930 242525 999909 526232 999933 350530 999959 800076 999982 360729 999959 540590 999944 947910 999970 180878 999983 397129 999992 308186 999924 917915 999927 492353 999914 512661 999932 597772 999951 420384 999959 200758 999975 457960 999931 642903 999984 798960 999922 982583 999984 235400 999907 949483 999937 235679 999971 205852 999909 196584 999979 697983 999923 822429 999926 528621 999983 975906 999940 786163 999936 279840 999929 436838 999966 397100 999991 500875 999936 408870 999901 997473 999903 92504 999998 985063 999953 30613 999958 328983 999919 924874 999998 321266 999970 136884 999955 543796 999925 963959 999983 76513 999990 51699 999967 424023 999942 8799 999946 878680 999967 15642 999978 459437 999992 676211 999977 17259 999989 305514 999987 582247 999929 715671 999960 832165 999961 67021 999916 378416 999991 557766 999916 313696 999952 348890 999925 899952 999958 733934 999976 329494 999972 512931 999980 417623 999902 300206 999968 874289 999952 401092 999950 985934 999941 565586 999941 651010 999988 572157 999914 864113 999994 108290 999962 664666 999944 297663 999938 133464 999979 987081 999992 390647 999966 308077 999936 17245 999947 75275 999923 690065 999948 34521 999971 384276 999928 618393 999971 916091 999961 597515 999996 513622 999908 890499 999922 920585 999948 875720 999906 208512 999959 773432 999915 877980 999964 549744 999973 151759 999911 844668 999983 528598 999918 685532 999945 278833 999951 693948 999918 521370 999922 102502 999912 206525 999969 943386 999986 896694 999958 222207 999942 529887 999984 674453 999945 438292 999993 933371 999928 471717 999926 797517 999949 279773 999953 506803 999963 278448 999999 25803 999966 276157 999956 126231 999940 647922 999998 319957 999976 76460 999942 214528 999921 507409 999915 881175 999947 370708 999918 489516 999912 275667 999942 151287 999985 74855 999946 123177 999915 128999 999947 639456 999995 380887 999962 86333 999949 403988 999943 369578 999935 619694 999940 803669 999936 269428 999984 710567 999990 342039 999979 74980 999990 663084 999908 265961 999913 207007 999920 720641 999947 437562 999974 758893 999986 670188 999996 980097 999985 758420 999912 374619 999933 227890 999907 715858 999909 462654 999939 731401 999974 764889 999940 578237 999985 828690 999998 449447 999955 233950 999910 488927 999904 15065 999957 30920 999986 501619 999917 161138 999944 624753 999928 406790 999997 712809 999904 811400 999969 171112 999937 33876 999986 679764 999956 429188 999986 772118 999912 433389 999932 769341 999914 970269 999907 488721 999954 376693 999915 376968 999990 771900 999967 680920 999964 135299 999987 709271 999977 754505 999901 208188 999913 255057 999973 95772 999927 28850 999920 733852 999961 154498 999995 30872 999904 95278 999995 793318 999955 491918 999952 240201 999911 149369 999913 388582 999982 943092 999941 267088 1000000 319655 999983 898765 999972 931172 999996 24219 999966 980919 999976 146926 999991 590926 999996 864411 999980 598308 999954 116335 999950 520783 999956 88696 999977 752135 999966 651751 999975 747511 999912 921706 999949 666559 999916 663027 999982 750755 999930 844882 999923 948897 999993 49727 999992 655026 999919 500493 999917 450615 999945 385070 999907 511859 999985 964082 999904 452004 999926 113176 1000000 62928 999940 20870 999939 154578 999967 491453 999936 689520 999979 814855 999953 272803 999902 307776 999913 324301 999970 953510 999952 852759 999956 833664 999904 624965 999935 131010 999987 960642 999991 888634 999990 826606 999980 546419 999999 225364 999906 353586 999943 718792 999960 29278 999986 769401 999902 699746 999909 617009 999988 387824 999945 854297 999995 122738 999941 107 999941 85958 999916 675687 999969 637309 999921 29824 999979 830492 999993 37455 999906 982147 999955 744807 999954 354757 999901 577543 999924 323414 999906 630723 999947 284437 999935 637643 999980 732462 999922 593740 999924 886426 999958 614139 999958 394585 999976 171861 999966 593696 999917 975548 999973 605891 999957 618139 999962 500555 999994 372967 999972 950930 999955 307460 999940 937408 999961 564163 999990 364591 999994 761503 999986 251573 999959 732107 999939 448067 999977 966279 999924 556513 999993 622369 999914 640923 999917 526250 999905 448170 999901 532715 999990 785631 999976 549879 999929 150682 999978 772804 999912 586300 999982 908755 999906 514209 999984 538015 999958 401056 999994 980020 999997 35721 999947 129990 999977 574589 999968 220395 999973 171786 999996 319802 999958 663729 999933 306365 999997 70874 999927 227557 999911 12212 999989 884868 999985 226931 999983 498729 999981 560619 999980 681838 999937 908933 999903 365642 999973 413047 999969 404752 999947 308594 999939 527288 999947 472850 999971 398847 1000000 946487 999910 236043 999929 369303 999985 445106 999945 400863 1000000 958935 999902 398827 999907 543845 999913 670478 999920 880160 999967 860507 999958 886952 999934 423492 999995 137237 999903 56287 999991 130498 1000000 752885 999970 495597 999979 252791 999968 931935 999918 216759 999984 353131 999905 601552 999943 277618 999937 142641 999936 322966 999940 187745 999915 837126 999947 499865 999919 562598 999948 71903 999944 946774 999977 274906 999956 904265 999995 375645 999928 699216 999994 860698 999959 935472 999909 89011 999945 29792 999942 609404 999989 550328 999938 5786 999908 976431 999993 864835 999991 327156 999987 756589 999935 822508 999914 930718 999985 612404 999910 764188 999946 150250 999941 717348 999912 643104 999907 663990 999990 366237 999967 670616 999953 818938 999979 299441 999951 494504 999942 544247 999981 716946 999949 592217 999921 609160 999924 242698 999908 78998 999946 125468 999984 926074 999919 216656 999980 251836 999914 13513 999942 759976 999912 580443 999917 932183 999950 546191 999953 139383 999943 487830 999987 746103 999969 927559 999920 217504 999944 632815 999902 960079 999911 631012 999995 556352 999971 733752 999947 716856 999993 893024 999985 533475 999970 192527 999935 293029 999902 484251 999954 568943 999919 456827 999903 127984 999981 367054 999929 316607 999911 739074 999975 480871 999969 18248 999971 801608 999994 508873 999971 557112 999902 133246 999949 84960 999924 248617 999948 386415 999923 372100 999976 392815 999920 672053 999945 49454 999901 974270 999977 697628 999921 639570 999980 166732 999939 928486 999954 458597 999951 509436 999979 741999 999978 278958 999915 133079 999973 728196 999970 949837 999948 852662 999914 734897 999974 231038 999903 205627 999908 493555 999935 758903 999943 240284 999942 118460 999909 267696 999982 394359 999911 274181 999976 438215 999922 29966 999978 490717 999986 261585 999999 655692 999999 409603 999971 376312 999985 893329 999916 671890 999996 687185 999904 55011 999987 572604 999963 563805 999968 437463 999905 53605 999960 424357 999934 723095 999970 866886 999980 59338 999984 577438 999955 518436 999918 855838 999910 418219 999918 666551 999920 998756 999907 526783 999981 628275 999987 169779 999979 915958 999930 862035 999949 195407 999993 412119 999985 9992 999934 773950 999926 989507 999920 327584 999959 989212 999901 804702 999971 22252 999954 604506 999963 337109 999921 377290 999927 748228 999997 930575 999942 572870 999929 924360 999918 214722 999933 65931 999992 157615 999945 533457 999961 626140 999961 939600 999983 350019 999954 607852 999930 516634 999982 564706 999944 125695 999968 623228 999930 210333 999971 417031 999972 807007 999909 410250 999994 57989 999972 810935 999946 711023 999932 321756 999976 623386 999956 258726 999927 206945 999959 285192 999918 15949 999907 172542 999903 429631 999923 420881 999911 280391 999914 354850 999963 631281 999935 911874 1000000 962761 999945 789440 999992 771254 999927 586491 999978 539362 999991 646685 999919 483510 999914 552063 999991 478381 999907 133710 999908 928290 999938 424211 999943 205333 999990 66000 999985 677652 999910 23741 999942 524783 999912 913564 999908 974150 999914 476921 999995 396371 999999 735148 999957 534353 999980 706390 999985 247865 999975 112624 999997 92017 999919 657516 999927 742236 999982 954198 999954 178355 999992 256028 999939 836079 999994 343219 999907 630293 999994 747690 999945 399442 999971 844959 999961 572693 999911 229563 999903 405899 999932 551706 999987 961867 999971 334215 999989 469201 999977 4523 999996 204991 999932 388219 999910 70939 999940 475911 999958 948702 999961 226210 999922 574678 999950 246169 999937 859105 999956 70369 999999 408217 999949 838421 999910 839295 1000000 233115 999988 399311 999930 73601 999997 843269 999988 917934 999972 87242 999962 103104 999928 255546 999907 815538 999913 345469 999933 20253 999993 216592 999947 61166 999998 590027 999939 336585 999994 672484 999977 942227 999997 225529 999911 198285 999995 172190 999989 955709 999998 371419 999906 677571 999981 641294 999949 344706 999929 997488 999989 683850 999949 531239 999975 792642 999975 923184 999930 236155 999943 915472 999930 256861 999946 68897 999963 288770 999939 297784 999974 775576 999919 756126 999974 562912 999901 356682 999924 278630 999976 944475 999936 181045 999997 294007 999938 849468 999948 934614 999936 335625 999973 199185 999946 204772 999932 364769 999919 185021 999985 690028 999994 989188 999958 450346 999970 816865 999907 231737 999927 812159 999925 164864 999985 195242 999995 844236 999959 457944 999992 883380 999953 421086 999936 623686 999988 180071 999967 445456 999968 96689 999920 924133 999977 304929 999991 594296 999989 657369 999916 142309 999946 981708 999965 243747 999902 195586 999949 914170 999929 311049 999981 393166 999906 849875 999924 164442 999968 589692 999936 276244 999992 999914 999982 280491 999961 147309 999936 260592 999922 280571 999928 809449 999960 407506 999989 285254 999951 68392 999966 494563 999940 621910 999903 168411 999973 815009 999902 563267 999965 808456 999930 850179 999939 206662 999974 50246 999917 145535 999903 891054 999920 525957 999926 110394 999971 92550 999983 271361 999986 187542 999982 275502 999941 702790 999926 806547 999939 876707 999941 764538 999990 867650 999941 517110 999940 779454 999951 262536 999905 469161 999912 726834 999911 687836 999961 216797 1000000 159782 999945 312125 999945 537894 999939 628612 999956 719831 999921 783844 999930 222555 999988 434372 999971 960047 999935 809130 999999 459522 999976