1 2000 1995 576766 999973 650341 999917 278185 999951 499942 999938 713520 999980 780034 999969 689215 999966 334466 999968 516067 999983 720217 999913 861218 999913 44602 999957 96597 999916 306895 999901 191974 999908 737360 999947 659023 999918 479683 999936 70305 999976 298536 999986 927865 999958 602576 999974 165859 999962 494932 999959 177035 999965 67994 999937 387589 999958 732265 999982 761793 999941 439704 999962 164882 999965 484352 999995 25027 999942 595528 999992 283453 999979 882380 999909 228487 999948 947178 999943 573802 999903 219572 999916 236294 999932 211798 999938 409260 999919 124564 999937 366583 999953 765682 999987 737392 999917 349346 999926 802411 999972 808556 999993 585234 999940 854827 999928 695976 999953 408504 999977 990744 999916 517625 999906 23587 999990 944725 999944 959210 999992 913144 999910 207491 999938 985188 999972 44187 999999 333472 999961 483503 999995 248129 999909 94841 999914 702491 999947 817122 999918 281945 999973 927665 999976 136313 999958 668336 999958 107104 999963 692404 999937 221259 999989 244882 999922 305608 999918 286851 999984 793576 999962 859796 999929 708653 999902 9540 999908 245497 999941 183489 999989 840718 999970 777766 999935 129011 999980 858400 999931 904960 999978 439143 999987 268280 999940 42467 999955 705174 999951 652273 999932 928267 999915 253227 999964 150415 999983 222259 999907 986895 999951 206924 999994 381388 999994 477635 999983 127122 999956 796842 999924 808374 999952 757180 999955 450632 999956 630426 999968 615469 999920 174602 999936 5307 999924 712485 999925 878607 999916 859822 999959 761668 999925 836909 999933 381123 999985 168425 999927 905816 999946 5318 999997 151145 999965 200974 999904 660893 999997 846566 999988 358131 999959 375191 999928 369096 999995 328305 999908 188724 999966 901414 999941 614971 999989 174505 999918 524290 999914 377812 999904 344591 999968 352542 999963 875213 999933 555694 999976 949301 999969 614850 999975 10554 999927 464640 999904 664274 999971 392211 999914 583460 999906 713184 999964 2561 999936 447779 999961 541494 999998 656559 999990 633769 999928 71277 999988 594319 999971 804874 999948 438494 999964 272380 999996 736856 999923 971900 999960 877477 999992 191925 999982 852739 999958 940114 999954 74005 999921 295986 999943 135973 999987 162039 999959 895626 999905 285607 999957 81145 999910 174102 999926 695062 999931 73180 999971 447206 999978 410599 999976 50202 999932 367197 999944 326444 999913 274479 999930 486248 999912 529429 999919 823472 999926 702423 999986 113580 999927 713760 999972 463173 1000000 844254 999931 88443 999939 663845 999919 593669 999924 420193 999945 958913 999928 623 999912 228190 999955 37021 999967 362956 999927 643234 999974 649259 999933 116262 999950 942980 999937 739847 999996 130341 999906 236169 999951 463285 999934 661488 999962 261724 999921 247640 999998 617851 999997 962420 999937 768350 999994 812298 999990 800681 999944 281687 999943 814410 999913 895187 999999 491612 999936 337428 999912 423722 999991 274773 999960 426742 999907 402125 999985 700855 999987 727132 999939 514519 999923 963894 999995 796906 999904 764708 999988 461847 999956 286542 999910 234044 999961 894162 999944 142972 999936 427514 999910 647084 999908 746234 1000000 665611 999964 882925 999915 871118 999977 52266 999922 632803 999908 533776 999932 41087 999987 152190 999993 941500 999968 209025 999916 237872 999968 974880 999945 162082 999911 73643 999922 601817 999951 539673 999989 993158 999943 700887 999922 748005 999957 938413 999985 221608 999978 852461 999946 655683 999919 448243 999989 440637 999968 695557 999976 862932 999902 699364 999985 794474 999903 136858 999977 195036 999997 633096 999932 544657 999952 774071 999910 444917 999986 375850 999906 800024 999940 523136 999934 153198 999950 310233 999948 261 999957 317667 999982 635316 999993 624983 999948 266173 999940 431574 999975 55407 999936 323443 999954 463826 999935 85561 999925 350160 999906 303726 999987 728851 999963 713155 999950 619591 999905 721440 999965 328012 999947 786942 1000000 725745 999903 42475 999913 511326 999921 616684 999977 162003 999969 253672 999959 381239 999927 751592 999949 179672 999928 273771 999987 185783 999924 966013 999952 306596 999965 141849 999937 397990 999944 341264 999984 427311 999968 488977 999993 120158 999932 537902 999985 628097 999983 706120 999908 95586 999967 932977 999982 910109 999978 870558 999973 378407 999966 150728 999992 473908 999948 11339 999995 916266 999902 135644 999903 729378 999954 608435 999947 828290 999916 945246 999923 456295 999914 484848 999976 334428 999976 271562 999931 942278 999970 967009 999903 16281 999904 216733 999970 549645 999930 982313 999925 326131 999939 153457 999915 720705 999914 844647 999990 61749 999908 237083 999937 123316 999977 135500 999970 925952 999901 526445 999982 914896 999978 838045 999992 935524 999919 682093 999984 552922 999909 416942 999911 691351 999962 226990 999912 173939 999938 562094 999989 31280 999942 817179 999931 365398 999906 549588 999945 203440 999946 953943 999986 217167 1000000 196153 999947 627344 999968 554765 999902 691364 999986 134003 999902 643706 999992 844118 999920 658312 999922 655356 999926 471588 999957 692297 999970 641993 999932 301182 999992 258694 999943 763995 999995 501269 999957 204185 999997 184405 999914 653085 999910 675849 999945 613455 999972 902121 999907 94836 999924 852444 999955 301313 999921 470389 999913 399570 999992 909473 999907 210315 999933 789330 999937 647035 999993 816008 999957 142118 999946 182688 999948 181147 999936 128639 999904 968899 999913 696652 999955 95829 999951 108642 999905 928179 999986 158413 999941 872758 999940 967121 999964 64611 999972 863315 999968 310327 999952 283352 999905 396534 999909 893675 999994 166790 999999 298808 999914 860368 999968 866395 999946 784847 999944 101120 999947 589101 999987 996936 999995 850808 999913 141190 999987 725974 999956 723653 999943 81197 999971 773093 999942 147922 999966 471754 999990 174055 999926 855898 999975 233189 999961 590118 999914 394451 999997 753292 999910 451646 999979 609101 999977 745796 999926 537477 999954 469335 999928 967735 999996 951897 999991 652486 999991 366532 999953 301360 999913 60831 999996 626241 999997 922779 999984 975080 999905 974859 999957 647245 999953 578428 999972 737302 999962 564954 999905 64346 999906 429434 999994 433189 999988 870697 999950 67942 999966 959383 999942 94254 999915 994681 999983 822971 999992 924255 999931 143600 999914 185779 999986 963978 999937 452847 999958 676975 999934 895084 999914 115404 999954 767093 999980 3716 999923 146562 999986 921132 999970 205398 999977 744906 999927 21606 999950 398914 999989 547016 999999 200509 999903 910469 999949 719925 999905 92407 999933 607863 999973 328495 999977 36492 999903 292491 999923 887820 999994 838736 999969 942000 999991 942387 999985 223349 999974 178393 999948 197406 999944 59471 999946 341752 999987 660405 999964 446565 999907 811480 999929 495717 999996 586740 999974 703660 999901 290722 999929 348146 999933 851739 999984 656706 999941 944440 999988 897518 999923 404704 999907 929470 999934 225635 999917 460071 999908 603741 999973 256285 999931 153100 999955 906289 999944 359174 999955 976403 999931 133795 999973 318399 999993 938066 999982 549522 999924 779046 999945 697935 999907 525930 999954 18934 999972 770217 999922 503460 999999 861688 999960 630019 999990 263770 999908 387954 999956 387458 999905 914365 999949 787027 999912 468355 999936 219120 999974 436930 999935 239728 999950 322225 999939 866282 999919 780727 999930 828965 999906 121118 999925 454172 999923 162979 999948 659584 999958 524115 999966 711472 999994 445935 999914 931536 999987 110139 999988 734032 999961 943535 999912 328568 999936 716242 999903 883139 999918 401674 999940 191819 999963 592602 999961 930861 999950 66789 999939 706872 999947 901803 999953 74056 999926 41665 999964 456563 999988 240544 999977 164209 999953 492692 999984 288174 999982 49844 999928 631063 999983 335795 999921 774892 999944 54800 999984 263315 999986 103427 999981 232571 999983 943744 999986 932295 999922 24369 999936 276204 999905 961841 999978 724843 999929 170409 999990 529645 999959 191992 999909 257313 999993 557137 999927 119467 999967 329402 999953 416916 999951 402472 999999 2060 999976 764759 999960 537804 999932 423905 999931 791987 999999 949361 999986 767720 999923 899582 999960 299706 999990 383472 999964 912593 999987 557092 999976 780697 999939 995948 999970 994545 999995 529562 999993 666403 999955 338474 999950 795327 999925 584864 999938 978197 999969 125506 999936 352205 999985 426578 1000000 219023 999996 333777 1000000 610664 999973 515434 999941 246415 999928 547550 999975 138129 999967 991268 999906 339740 999969 864577 999938 47993 999961 502186 999923 159100 999988 775784 999999 975110 999952 345496 999995 652017 999988 264880 999944 142149 999991 746501 999979 240919 999960 742145 999988 330076 999998 492291 999915 817503 999904 552828 999977 910091 999993 876263 999926 847675 999925 937034 999921 566216 999922 647229 999977 332499 999939 676723 999941 789121 999956 365656 999930 764655 999925 559295 999941 10783 999977 773490 999936 111419 999951 84624 999927 967819 999971 817066 999993 943970 999995 210832 999961 920398 999936 149501 999977 375750 999935 669870 999916 105090 999910 180710 999930 390903 999950 137046 999948 743490 999951 437566 999990 953885 999995 471530 999959 696745 999971 312562 999953 130580 999941 835034 999915 110606 999993 130008 999952 319022 999977 483209 999996 490426 999968 153137 999939 92394 999915 271627 999945 351570 999941 430984 999976 504971 999959 764998 999905 92630 999989 707332 999907 706716 999989 646774 999963 195227 999910 417096 999943 584022 999903 71362 999913 262360 999931 260268 999953 888873 999976 700286 999962 830 999996 828717 999987 281507 999983 937458 999943 794188 999992 403219 999977 849724 999953 794496 999935 944147 999934 795319 999904 970082 999994 661322 999991 441891 999933 964482 999917 479757 999908 88424 999928 375831 999949 855353 999974 419557 999915 662345 999956 574119 999936 616365 999976 467505 999960 914091 999976 808022 999973 239223 999984 941294 999997 857841 999937 46296 999906 367545 999926 718559 999989 618368 999903 150163 999977 192967 999993 271393 999907 108800 999988 70176 999940 30004 999925 225873 999908 921002 999909 784894 999993 360068 999982 726077 999934 430782 999945 522569 999948 311531 999985 839864 999937 876777 999920 917410 999938 814297 999947 445133 999967 179677 999952 917691 999952 879301 999961 769300 999920 182661 999998 562792 1000000 410290 999999 778377 999910 519655 999940 874663 999985 217490 999996 266819 999942 43701 999925 212856 999989 923471 999952 697161 999949 443871 999915 64999 999965 366839 999995 429881 999940 868981 999979 590953 999948 14711 999960 154197 999905 257968 999976 632009 999970 840837 999936 114490 1000000 717182 999940 518266 999935 624841 999935 378493 999952 908168 999934 886080 999981 478890 999954 540944 999943 966660 999994 616541 999956 457890 999928 621514 999992 290871 999974 665529 999914 892850 999971 426187 999973 676068 999915 115483 999905 992357 999975 850638 999962 154530 999972 233355 999997 267249 999979 918049 999941 952087 999937 475168 999914 954599 999918 429660 999913 511701 999995 577132 999977 125205 999973 457502 999932 92156 999918 617291 999986 543089 999991 777782 999916 780992 999972 334920 999911 683397 999962 849466 999956 807247 999905 784141 999935 184975 999924 832438 999972 797695 999984 188017 999903 800606 999996 731927 999988 782025 999974 82047 999983 560459 999968 843431 999930 209364 999998 134973 999905 702024 999928 55148 999965 285916 999958 276279 999926 909911 999934 106360 999977 78666 999957 281900 999933 698209 999961 700800 999985 655899 999912 683438 999981 723119 999951 924388 999962 207383 999903 418992 999956 757755 999965 379821 999935 704263 999978 310996 999920 898725 999961 174373 999953 536574 999966 216364 999992 717682 999939 377814 999907 433193 999971 644322 999945 651404 999990 753663 999945 71758 999965 254889 999964 494858 999913 753293 999940 213001 1000000 846328 999988 922416 999984 115695 999935 754666 999948 352591 999904 255809 999914 125779 999911 273591 999920 105335 999991 551066 999931 737647 999937 772475 999963 147232 999991 100933 999982 298002 999922 312403 999923 553092 999936 426275 999936 831911 999937 254510 999947 608394 999958 933346 999912 211652 999984 766499 999960 323626 999915 73184 999941 191441 999950 638987 999957 281157 999923 618514 999947 199799 999961 34330 999996 342110 999976 296784 999951 494551 999942 45981 999978 865369 999970 274801 999978 851094 999954 530318 999968 627982 999964 677445 999981 864155 999994 791515 999963 373289 999909 499074 999915 74391 999907 204613 999935 805180 999948 733197 999995 282832 999926 872388 999976 242057 999949 118432 999988 353705 999912 351785 999953 489445 999923 149487 999918 919486 999984 312070 999946 893168 999970 501133 999929 442896 999914 43979 999907 848501 999998 904781 999935 231992 999968 690124 999977 135564 999975 758746 999931 268852 999989 188241 999970 315129 999983 500588 999995 633304 999998 250286 999935 797477 999925 156943 999939 544116 999999 27851 999988 487636 999913 686317 999901 687243 999944 856273 999908 503674 999941 90688 999994 710080 999979 669088 999991 43938 999980 558812 999927 871841 999934 919138 999942 816341 999963 86870 999978 346110 999933 159383 999950 607575 999905 467532 999953 299811 999927 856679 999963 6201 999949 115023 999941 649161 999999 661639 999982 613404 999955 281174 999926 787138 999965 546279 999996 323838 999952 183047 999937 914863 999958 511051 999928 652577 999906 889721 999916 123397 999931 933972 999958 720753 999928 946607 999992 319704 999915 230069 999991 137607 999991 231443 999907 803620 999905 920189 999917 612253 999953 641144 999962 586627 999979 990847 999901 611324 999929 350060 999973 401215 999913 349304 1000000 981582 999916 595439 999959 530604 999985 438002 999956 813981 999951 331644 999969 367627 999933 516637 999982 2406 999947 112987 999902 39486 999998 43403 999904 762718 999965 607291 999954 199813 999997 696858 999935 994480 999986 256606 999941 184558 999927 459443 999988 106661 999940 185001 999976 122940 999997 696698 999976 636113 999961 182850 999973 974383 999934 949634 999960 827631 999977 986083 999967 655936 999916 776385 999952 462328 999932 741228 999973 366806 999913 924938 999941 678896 999990 767505 999966 31512 999996 841732 999990 913206 999972 71463 999949 204202 999962 697443 999911 230942 999916 107676 999912 172209 999901 627852 999928 623008 999999 436134 999959 50868 999935 822879 999913 887651 999997 861603 999909 420549 999971 615302 999979 105824 999958 756240 999962 704261 999908 335793 999910 616704 999948 683318 999925 291493 999925 100481 999982 179669 999908 978238 999993 254753 999903 809630 999986 349471 999996 560032 999971 502516 999915 227084 999975 369284 999973 657100 999946 554946 999948 752101 999993 780136 999919 997205 999985 489334 999909 225032 999967 273802 999968 853430 999991 25879 999926 514458 999975 617588 999991 641312 999995 114194 999949 595761 999957 782643 999950 973739 999912 976000 999912 193524 999918 640965 999954 906458 999924 585845 999919 275753 999947 949899 999917 39390 999955 947926 999908 835904 999903 303372 999986 20556 999935 16756 999987 145955 999947 429228 999930 404454 999998 290320 999946 576314 999966 699962 999918 69237 999990 391324 999927 617039 999918 855403 999953 691087 999984 844080 999997 322580 999901 87496 999958 368169 999978 768859 999947 717279 999912 137276 999994 822187 999999 438567 999914 38302 999915 195562 999969 279331 999927 137619 999962 419549 999994 72379 999956 537272 999937 445730 999906 840140 999941 774405 999964 723853 999906 890902 999963 75139 999915 893128 999959 735245 999989 657742 999953 86928 999909 931225 999924 900830 999932 162237 999997 611059 999931 440053 999923 190431 999902 478834 999981 127754 999906 784229 999976 470103 999957 827077 999997 32004 999910 176689 999901 649669 999977 626309 999913 921726 999904 205721 999999 552808 999987 346768 999976 854289 999929 277049 999924 216018 999904 37268 999980 393293 999933 980925 999977 667144 999906 992388 999998 935913 999962 51643 999904 743325 999935 29428 999902 347992 999968 24964 999982 545448 999936 702887 999919 275236 999978 344861 999966 542612 999996 486229 999910 192804 999957 480222 999929 162292 999945 405745 999998 961029 999933 598911 999958 967716 999976 446994 999967 715845 999914 324050 999966 273047 999961 456147 999902 560403 999939 595011 999947 999350 999989 222913 999993 730528 999908 48454 999998 822875 999952 162380 999918 906273 999953 948503 999993 622098 999974 533192 999979 737660 999904 229503 999983 422893 999960 140179 999928 617744 999965 334318 999937 609808 999994 364788 999996 159998 999974 888714 999901 552625 999945 555671 999937 239157 999941 680563 999920 154720 999933 273245 999967 550153 999969 795135 999991 510191 999919 769644 999904 959001 999944 762279 999961 792654 999957 890813 999936 31702 999955 410102 999988 143035 999987 86995 999986 479342 999974 459933 999964 543016 999926 997998 999920 920362 999905 176548 999999 591741 999931 695512 999988 950959 999947 78624 999980 699498 999918 664520 999928 606041 999954 912965 999933 5754 999997 346525 999929 926501 999927 964369 999904 882353 999926 28039 999966 194565 999963 553033 999996 49932 999917 320204 999977 373563 999989 685815 999975 352661 999991 371500 999964 11074 999943 855995 999968 440718 999911 892293 999970 627163 999994 688879 999933 440840 999975 336308 999979 907805 999943 624468 999939 641817 999914 733236 999951 933325 999977 892750 999903 49862 999984 936365 999923 988349 999951 213231 999930 307640 999911 766345 999904 665146 999967 788725 999952 269830 999998 510173 999943 740999 999956 26223 999906 727451 999914 263039 999988 150763 999913 557566 999990 814022 999961 177325 999947 652977 999901 304271 999954 264393 999920 916567 999988 264151 999964 728275 999905 995322 999985 47229 999909 291853 999977 912468 999938 827213 999972 66617 999929 939065 999950 648141 999998 181118 999990 527068 999922 854858 999959 809934 999995 749536 999991 984311 999903 325951 999981 188656 999922 769126 999974 126527 999952 236355 999921 780248 999921 414198 999942 840129 999927 420585 999987 731380 999923 764555 999945 624897 999984 103825 999985 540015 999910 582314 999981 902201 999975 75546 999945 740497 999925 445915 999982 990171 999970 795511 999940 930966 999921 313498 999953 167375 999930 456007 999946 170276 999956 160947 999955 166195 999988 867986 999926 266658 999974 359723 999910 679038 999958 992816 999936 467233 999937 900712 999953 848072 999935 775254 999995 440200 999974 244278 999985 169785 999968 938387 999922 434033 999946 220231 999971 719658 999910 638047 999991 863638 999977 23592 999933 125793 999920 611520 999932 623071 999985 655210 999993 636019 1000000 596751 999902 436648 999906 740848 999979 918593 1000000 719742 999942 146691 999939 507141 999932 804445 999912 365337 999909 265495 999953 555779 999904 688100 999948 154789 999986 466973 999971 794779 999925 648793 999953 215121 999959 204908 999964 473521 999958 727879 999906 536126 999939 265337 999965 673617 999927 410345 999982 302307 999945 855573 999969 575254 999905 172038 999933 134784 999949 132203 999958 156887 999950 451989 999927 976147 999964 234873 999964 316463 999933 643350 999962 378243 999953 300741 999935 443029 999919 606144 999919 276245 999981 820867 999987 222130 999928 626273 999971 119889 999939 818112 999986 420728 999905 390898 999976 414754 999981 906817 999990 44221 999976 579197 999970 797448 999984 18517 999981 543582 999924 607475 999907 282651 999948 220353 999947 639493 999973 154139 999925 293925 999916 283236 999974 688199 999914 576083 999911 70129 999932 968019 999901 998449 999905 433540 999998 814283 999967 996065 999935 83689 999954 161881 999947 368953 999947 406354 999902 692517 999902 892481 999978 658695 999939 305039 999909 296185 999989 868851 999972 882236 999915 214625 999959 84713 999960 511474 999904 928063 999949 787193 999944 415331 999972 81667 999946 59662 999983 245702 999916 291992 999951 401440 999953 375985 999905 545193 999964 569656 999982 564046 999942 176532 999982 910972 999966 702202 999935 619092 999982 442237 999929 253325 999961 123170 999927 836232 999937 322783 999968 610520 999950 916064 999941 785749 999937 113360 999981 609564 999998 719965 999995 276838 999978 77281 999932 340314 999963 459899 999991 932269 999935 301314 999957 661220 999913 661557 1000000 532886 999910 750068 999998 763778 999960 145208 999977 70388 999991 890116 999982 701908 999927 138406 999902 177311 999983 90669 999958 284748 999980 170051 999924 126152 999964 923095 999959 501149 999982 667127 999990 184594 999902 71791 999984 472185 999964 891102 999906 498300 999986 652001 999970 101018 999919 314321 999971 841417 999919 997461 999902 449010 999914 940284 999991 701486 999975 606166 999942 833650 999942 520946 999941 763512 999909 554572 999932 605705 999968 494484 999995 440343 999935 179246 999954 958625 999943 392075 999952 456697 999982 491839 999970 674742 999966 307455 999990 201531 999990 747949 999993 232089 999923 513949 999955 324293 999924 919330 999966 597604 999970 353524 999937 910149 999981 460962 999931 286429 999967 272212 999928 85686 999911 439756 999989 993079 999977 674994 999944 543590 999986 914789 999997 740655 999920 981275 999975 780640 999916 812494 999925 370705 999970 896012 999997 895213 999937 514001 999988 40160 999947 377557 999922 914274 999924 166382 999995 12689 999944 559249 999951 189896 999942 85989 999936 40837 999913 17220 999914 662968 999953 124782 999939 597410 999987 313755 999981 704413 999923 88235 999977 911385 999921 853204 999921 555631 999931 509867 999908 267004 999917 922763 999931 984741 999903 624805 999916 643330 999962 453239 999911 565545 999990 895690 999982 757862 999978 693999 999930 445899 999973 840307 999981 14638 999956 451700 999988 528403 999905 649925 999937 381573 999944 642521 999973 9318 999931 966838 999969 252953 999973 558072 999941 286573 999965 717757 999901 37062 999983 752865 999929 831350 999919 746575 999964 134071 999975 569706 999988 907604 999995 721847 999908 473199 999924 992150 999997 699449 999938 415291 999903 438352 999940 151634 999966 124206 999993 392841 999929 431642 999974 929941 999986 944152 999926 318219 999901 164824 999902 997338 999944 35906 999920 767226 999907 511247 999978 959231 999905 584474 999977 568059 999984 244376 999968 975318 999999 127433 999936 360861 999974 400509 999986 795014 999966 685603 999910 329758 999928 606069 999997 160671 999999 59900 999915 132576 999971 518619 999991 834836 999983 937150 999974 47209 999991 366019 999907 734526 999945 68480 999947 490061 999949 533495 999914 395403 999994 205633 999969 47737 999935 170769 999980 850950 999965 586329 999976 578783 999989 613286 999946 366000 999933 967852 999945 144368 999912 653801 999908 743581 999966 415645 999998 394419 999961 573930 999938 838826 999944 579332 999993 442510 999924 429085 999976 289559 999933 990106 999956 804728 999903 99318 999988 273622 999918 459316 999963 904550 999946 474560 999946 642403 999942 359806 999998 73 999976 389144 999944 842199 999978 595188 999976 508925 999954 183572 999928 475759 999979 990104 999942 301830 999963 666948 999902 578143 999935 615164 999935 222960 999992 906232 999973 323993 999956 43497 999938 552052 999960 840226 999939 47090 999966 633756 999978 401228 999901 64208 999971 514283 999967 495650 999915 216988 999916 266777 999966 49457 999920 556868 999909 761187 999944 613235 999956 881141 999909 574354 999981 308349 999964 908123 999975 693105 999917 884821 999946 997217 999924 717027 999909 239128 999925 765094 999982 120598 999940 119733 999924 391061 999902 315624 999979 768651 999914 614482 999922 704062 999947 274570 999980 127590 999998 567237 999904 402788 999906 510287 999904 485678 999943 207342 999929 290439 999913 225325 999950 328597 999967 931872 999934 268065 999997 912392 999951 926671 999995 241249 999996 516315 999992 788763 999949 601331 999944 472365 999932 392748 999913 476525 999995 302359 999938 822778 999975 205685 999905 267895 999926 240540 999987 351291 999982 613077 999971 958157 999938 412672 999925 671765 999992 384613 999921 794576 999946 977699 999932 977536 999980 995768 999938 744786 999901 894864 999985 184391 999933 661232 999958 32092 999972 127991 999942 843368 999965 426191 999992 33887 999911 853350 999960 807230 999938 518098 999958 338418 999959 953364 999955 193290 999947 476393 999936 666830 999901 627013 999992 345261 999959 484072 999960 223958 999961 448673 999951 245710 999972 30573 999969 91035 999990 531443 999985 92283 999924 144956 999985 213133 999930 775178 999981 74742 999923 855426 999968 218286 999936 622062 999955 981819 999904 688677 999994 826981 999938 448782 999924 420862 999930 763017 999966 482322 999975 665272 999987 995437 999919 628605 999985 9275 999969 75238 999901 532773 1000000 738456 999912 595579 999939 581016 999983 497828 999928 152979 999989 214087 999984 390302 999918 913538 999947 779124 999971 771604 999924 985113 999967 849538 999995 487559 999999 100799 999962 553650 999975 152050 999912 413009 999939 198292 999982 937028 999992 316419 999904 335807 999978 185386 999936 37768 999993 458328 999993 51509 999935 276508 999962 291089 999968 648568 999946 59561 999929 332808 999939 271441 999903 471086 999931 850759 999942 866449 999922 794288 999983 58050 999973 629590 999981 852526 999974 343575 999925 325402 999998 753798 999968 213771 999945 82303 999916 356457 999937 905819 999945 926830 999988 150097 999973 63938 999988 21295 999911 281832 999939 59161 999939 518027 999921 228449 999985 401021 999923 522445 999927 731933 999913 249123 999978 356669 1000000 158379 999908 570556 999951 693995 999925 504684 999918 692702 999995 307832 999946 993944 999971 71953 999902 521985 999976 413937 999920 460356 999962 41684 999903 920419 999981 396781 999950 854304 999913 676054 999959 792367 999928 261925 999957 645677 999973 325677 999904 521395 999902 550260 999934 684085 999998 37020 999918 45000 999904 133743 999995 750640 999908 753628 999904 47473 999967 364165 999990 583471 999993 749485 999965 780323 999930 971105 999937 907765 999918 120641 999935 457522 999964 83750 999934 625749 999959 862215 999958 926250 999979 552769 999982 494771 999910 637538 999943 270300 999960 788352 999913 652811 999923 383698 999976 470410 999985 812388 999919 655654 999985 461007 999979 492549 999998 644601 999976 170615 999921 713471 999950 496125 999908 837576 999956 455001 999992 107790 999931 688183 999985 770855 999928 880122 999943 230880 999941 924823 999936 76707 999938 819903 999947 179064 999923 993668 999936 989350 999932 931960 999909 840576 999910 657810 999973 837095 999922 649514 999954 919078 999924 828503 999966 75977 999966 778883 999911 15851 999923 536393 999961 996995 999993 60631 999980 704372 999972 230249 999954 444570 999942 457908 999998 538995 999913 595298 999934 465584 999905 994896 999944 158740 999950 403499 999917 637694 999938 738578 999994 783626 999967 232681 999945 908678 999983 278301 999963 913604 999911 959868 999920 454900 999913 145684 999902 916353 999914 151350 999996 618085 999991 296194 999941 155329 999994 67701 999937 343624 999943 591455 999950 847334 999965 40137 999970 410910 999920 662028 999952 203566 999944 256873 999954 480690 999986 46697 999928 96001 999992 502386 999903 485137 999974 916612 999996 432476 999925 916474 999927 109586 999917 972188 999952 673267 999922 427983 999948