1
1746 39
64936 595108 628237 709741 812917 1277432 2859360 2936967 3159666 3522591 4099253 4629860 4965322 6177198 6287861 6638687 7199377 7515120 8087729 8620940 10656485 10930110 11087293 11143455 11324576 11376013 11383057 12380206 12435490 13070917 15322852 16632947 17847915 17963698 19553648 19641447 19686852 20622665 21307877 22264966 22392216 24411987 24829430 26506041 26896731 27044745 27559910 28130303 30791059 30920824 31754615 32097309 32870964 33152119 33440155 38118783 39710769 40358889 40819337 40924549 41263551 41335064 41351670 41486806 42851674 42995053 43054806 45133835 45871832 46704089 46818667 46836696 47124372 47826060 48073972 48478176 49155514 49802273 50290041 50300873 51133339 51280869 51667417 53965103 54333668 55565642 55578493 55940594 56198871 57460257 58006553 58398147 60065495 60368094 60562483 61379600 62113545 62197650 62792363 62907095 63065087 63279782 64832411 64917707 65823856 67244382 67513496 68204421 68959665 69274033 69748161 69781244 70639017 70854628 72805631 73007307 73326356 73639083 73921058 74479091 74990963 78118962 78171674 78212493 78430250 79303801 79368482 80036576 80785802 84101515 84914368 85569787 85900907 87070531 87655208 88371685 89053740 89208398 90294446 90776023 91022078 91139406 91159788 92401337 92529910 93239059 93317631 93794811 94814294 94953294 96314943 96663570 96814833 97006278 97315599 97371772 97506817 97626989 97700168 98141454 98263920 98354188 98817436 98864761 98966080 99668326 99723753 100003191 100438282 100865064 101041972 101286303 102588856 103675319 103923319 104564154 105111847 106005163 106027829 106294986 106397077 106895619 107069455 107390522 107866169 108583335 109905933 110005383 110750478 110884409 111253073 111334032 111658191 111841072 112542828 113433686 113735400 114929806 115412813 115814540 117385968 119444869 121494979 122703882 123104574 123540217 124138025 124214184 124936142 125005996 125112828 125500030 126900689 128404183 129446652 130177175 130368217 130619239 131021900 131477515 131491575 131903008 132071985 133087186 133653541 134326476 134768466 134837643 135089159 135538914 136043424 136577929 137299764 137417763 137572725 138113047 138646906 138744274 141011338 141827476 143427327 143545211 143637371 143847786 144497426 144785965 145332277 145394582 146187289 146755849 147123241 147792677 148143826 148392990 149443997 149550246 150090587 150163192 151567987 152383887 152570401 154933940 155309501 155404504 155951234 155988060 156389565 156730636 157003926 158020710 158135187 158863905 159396702 160213079 160487455 161845921 162253417 162382726 162414627 163610048 163789401 164068265 164866678 165737420 165823087 166465718 167221073 167429814 168733041 169359950 169885581 171921518 171999630 173924845 174035772 174709068 174951435 176241286 176347995 176762947 177299617 178151699 178157157 178304058 179181066 180017144 180514654 181068403 181994324 182468405 182622387 182839018 183581928 184485966 184652091 185006021 186496548 188643394 188882879 189239055 189862691 190111327 190420362 190466481 191096508 191833714 191962488 192282733 195283828 195790687 196073533 196892118 197159403 199023676 199544363 201386202 201416046 201664138 201934043 202144943 202712358 203262664 203790761 204422918 206606415 208039892 208420246 208648831 209064181 209577616 209873837 210951713 211690548 212208112 212496041 212811691 213441537 213670756 213804208 214117432 214856922 215505523 215624215 216415524 217609831 218020210 218094063 218945101 219887260 220467860 221267913 221281308 221299972 222902258 223350134 223908193 223935321 224239178 225316673 225509793 225677775 225874678 226659660 227276898 227307322 229680355 230162002 232108964 232247271 232942751 233244048 233418278 234538184 234786450 235146507 235407955 235829736 236378906 236778321 236958100 236976129 237515992 238096419 238983496 239522768 239676683 239887232 240423230 240558185 240594325 240811115 242348018 242577531 243801868 244400741 245133854 246461236 246641067 247057170 248741745 249313926 250697651 251372976 251573613 251784776 251794563 253671398 255126369 255793574 256051782 257217040 257343268 257660041 257917226 259339869 259742345 260595965 260739364 261096381 261584064 262447466 262958947 263064927 264065510 264456880 264528171 264796806 265034849 265933469 267106914 267518201 267647785 267897905 268016329 268023672 268943550 270025958 270528036 270816501 271579511 271789017 273195694 274454584 276029649 276782912 276863225 279512644 279674021 279869059 280216046 280619727 281348796 281577460 283689494 284836906 285609342 287379653 287927613 288099974 288215134 291845121 292475710 292549577 293892261 293898402 294050486 294298412 294442084 294668990 297075339 297140101 297735232 298014034 299635558 299747755 299979356 300142883 300170339 300466544 300563062 300670363 302430456 302887443 303822119 304239546 304240704 304568931 305604703 305698235 307983102 308935311 309948009 310795860 310968471 311127916 312677046 312946348 313598538 313665018 313707121 315031125 315225714 315415754 316332485 316745261 318459094 319508364 319779236 320943088 321487096 321907379 321979861 322022056 323593242 323751491 326356849 326534284 327019695 327310314 328209795 328714319 329172345 330545858 331374601 331680777 331881349 332286710 332735405 332769302 333189240 333424694 333779735 334443588 334814485 334986423 335923570 336471593 337392176 337445537 337861337 339057783 339214577 339592374 339636494 343020903 343222597 343706605 343819841 343957078 344080465 344675856 346105599 346755130 347463366 347472349 347655350 348411395 348779182 350303899 350515292 351352039 351410555 352331487 352486274 352921783 353817594 353871649 354240934 354278899 354761501 355270570 355340979 356298141 356386104 356737148 357519631 357916149 357954671 358010060 358516342 360113178 360130228 360219199 361948851 362021452 362175874 366168376 366546016 367415367 368046353 368464677 368861375 371469336 372219441 372359494 374455101 374825448 375452081 375638061 376750746 376827413 377618555 378273518 378685577 379283737 379296942 379486044 380119929 380378263 382008950 382567502 383032973 385342105 386281270 386439126 387008439 387271651 388064482 388126597 389689290 389846518 390376599 390570689 394340175 394900267 396036125 397309409 397324904 397346469 397482778 397653988 398787600 399361579 399497629 399564414 399659001 399845696 400023226 400249655 400522332 400562820 400685386 401129407 401779019 401785917 402076751 403090318 404554543 405612055 405899509 407863355 408404240 409234456 409813229 409866493 410118665 411321058 411690550 412207962 412210237 412301759 412413244 413145535 413349817 414584142 414714237 414955056 415055431 415657704 415690244 415958188 416403469 417488199 419088396 419595138 419636474 419865321 420669572 421028416 422923379 423665672 423847132 424275433 424688752 425551069 425859156 425881160 427368518 427673808 427739425 427778603 427821877 428287373 428550442 428630452 429303483 429458862 430459954 430673474 431868176 431901297 431915653 432971354 433590857 433684116 433690539 433883384 434754900 435436214 435553835 436013245 436363000 438070947 439722050 440869784 441714610 441882966 442005957 442211579 442566130 443364814 443621742 444861924 445364372 448488370 448675209 449211292 450195182 450513423 450535676 450699795 451055126 451126532 451415411 452357510 452542854 453691849 455303728 456243249 457625364 459159716 459170465 459553805 460769087 461281034 462142204 463442272 464112005 465802195 466665210 467334263 467511719 467737920 467871450 468351627 468887048 469265267 469395793 469748077 471433723 471451982 472472678 472652666 474502211 475112333 477466405 477468614 480030290 480309196 480595434 481021861 481466661 482366437 482716729 483186948 483364791 483383453 486336682 486352170 487391218 487838408 488468001 489158279 489967814 490814269 491414532 495129394 495447358 495983990 496641775 496815632 496984010 497435819 498131884 500208901 500669297 501542008 501969578 501987095 502342643 502663133 502867385 503389726 503802577 505437207 505819695 506381045 506999939 508042581 508073816 508774743 509207324 509918972 510407721 511665547 511797943 512636290 513078169 513161213 513224364 513684506 513862997 514130427 515093732 515387386 515444504 515996704 516512467 516616390 516687063 518727179 518837587 519002087 519634855 519930383 521631831 522316823 524633072 525460202 525634542 526041137 526298488 527950218 528388115 528625827 528813366 529491300 529883715 530492938 531431970 531457247 531748639 531857766 532516056 533384052 533664830 534183191 534389173 534497978 534577187 534585809 534664377 535526239 536345751 536432277 536533452 536598869 537522199 537960797 538402105 539071526 539125853 539635435 539848389 539902115 540647794 541008783 541335180 541744450 541951064 542109340 543096948 543534339 544884918 544944320 545896715 546570230 546982434 547465643 548828404 549249359 549472154 550274442 550699196 551778242 552556514 553482996 553777681 554111284 556394635 556704891 557836046 558047482 558303816 558511197 559085834 559207317 559765807 560193724 561011460 562079626 562129631 562161504 562826646 563433988 563936984 564809544 567739353 568348101 568742402 569848716 569867243 570403430 570999160 571818319 571935216 573051963 574127031 574416908 574533541 575259559 575888035 575903114 577327398 577978451 578649823 578867775 581923983 583142986 583327243 583602347 583781349 583801812 583906615 585082227 586015978 586311959 586487562 586508017 586698589 587244410 587645148 588014487 589853479 590002320 590204992 590495978 590672226 590834916 591279858 591463835 591688555 592644134 593049524 594199661 594390217 594526342 594657155 596543016 596727778 596781790 597235965 597998840 598924839 599377747 599880284 600078127 600355429 600770279 601348301 601404283 601930493 602042022 602293028 602301264 603222645 604225819 604293061 604310506 604311870 605707260 606927016 608241592 608316786 608383081 608978985 608979218 609390205 610050582 610463364 610925076 612008593 612413710 613123762 613130877 613268593 616357122 616703475 617113011 617718066 617800651 618059959 618735250 619213996 619835692 620708280 621183851 621504356 621597130 622010789 622181669 622611879 622845090 623449152 623501025 625145488 625977002 626461289 626568495 627700694 627716945 627716996 627840957 627855022 628283726 628339161 629846333 629982228 630336435 630634113 631080974 631089159 631148430 631475203 632123565 632186927 632369804 633077609 633704662 633750576 633981048 634156868 634573040 634584089 634832978 638512516 639041861 639302528 640272270 641061800 641731385 641883964 642633637 642698470 643427517 644907015 645919668 646288432 646801396 647294027 647653245 647830541 647859923 647864476 648389316 648438805 649305354 649580684 650061759 651165457 651864899 651973353 652148293 652439612 653405971 653515497 653888016 654370751 654782403 655472889 655880151 657112971 657113059 657360854 657662506 658391110 658877154 659297780 659324206 659512111 659746103 660352212 664110326 664181622 664758422 665368477 665411388 665579302 666790911 666842645 667426348 668962747 670065289 670839338 671541958 671655331 673110632 673856264 674383317 674671195 675057662 676627916 676696959 676946896 677844388 678423379 678783297 678902099 679649978 680124560 680840964 680843861 681008202 681123631 681375470 681518169 682020361 682301149 682609321 682714208 683062684 683108931 683998088 685549759 686214352 686837575 687531334 687879459 687894709 688326888 689741895 689896736 689915911 690226931 690641148 690863728 691392403 691557147 692586316 693582338 693626773 693783896 694473068 695047037 695048593 695353014 696085026 696395870 696647811 697650521 697737660 697949134 698987877 699640111 699699767 699802504 699999975 701576389 701993952 702054303 702524966 702531910 702554909 703214374 703215161 703229905 703546661 704158671 704392176 705796989 705883728 706421689 706422910 706929645 707656695 708241592 708328338 708418791 708910832 709598969 711449980 712625982 713146219 714010223 715708023 715969601 716364995 716385139 716410429 716478787 716890521 717021955 717768982 717797616 718359053 718359190 718522041 718676835 718854704 718872974 719372753 719444268 720772491 721148441 721244030 722037186 722238416 722870300 723086765 723455015 723460090 723545838 723666645 724092475 724115290 725517005 725607957 725797749 725852100 726192827 726376279 727805208 727902293 729125127 729251949 729278086 730414404 731629636 731764166 731767208 732895748 733827528 734807265 734905651 735051569 735055501 735086066 735704255 735765107 735974828 736743896 736765729 737547107 738744568 738825879 739064509 739544147 739920644 740006275 740125183 741118531 741512762 744826015 747406474 747564470 748358767 748734919 749170216 750728210 750734718 750882735 751737534 752366076 753156984 753839744 754981785 755583078 756407457 756892985 757323676 757567026 757570154 757658569 757996792 758228874 758640440 758975796 758981702 759132934 759567396 760165862 761633024 761706927 761950450 762733417 763057007 763659786 763784042 764535363 766046158 767652889 768236624 769533139 770129823 770936918 771584804 772385567 772765311 774621407 774903135 775202439 776517814 776861760 777741797 777791625 777917639 778144881 778741915 779709623 780210155 780264209 781741910 781955389 782064960 784836427 784838419 786016142 786611068 786872527 788482196 788629388 789068646 789832418 791327083 791528655 792672786 792889791 793114410 793520770 795080101 796518056 797023317 797826338 797939096 798311342 799890476 801128850 802125546 802941940 802955019 803334388 803482172 803550610 803953644 803968893 804204353 804324989 805482343 805734019 806143087 806648609 807336575 809345521 809606559 809647950 809835495 810743768 811536717 812571037 813949172 813998983 814131200 814720751 815597138 816871232 818378623 818706121 818838327 819590276 819977639 820520936 821093396 821135505 821357969 821615178 821621145 821953485 822111389 823411748 823437992 823984492 824199076 825200605 825456264 826022615 826843830 826848830 826873776 826954362 827360628 827876518 827901385 827902845 829714433 829940252 830097139 830384860 830824974 830987655 831798529 832137047 833221883 833818711 833860421 834932452 835060637 835460825 835978850 836074388 836957154 837471565 837608574 838584695 838746051 839132583 839817749 843526190 843528512 843897560 844007422 844142933 845253524 847926687 848902622 849338266 849551378 850284051 850570308 850603127 851623613 851893956 852042936 852639189 853013166 853668957 853843738 855608125 855891385 856547092 856671378 857136304 857959779 858279716 858313089 858342866 860508653 860811009 861358311 861672434 861703554 861865482 862768551 863210322 863218919 864174641 865251398 865371453 866084872 866197944 866525762 866603486 868019728 868789317 870630799 870655180 870790223 871596081 871716141 871946361 872832572 873524414 873785959 873833840 874276324 875446810 875985019 876248010 876367857 877000178 877291698 878155800 878996452 879393493 879476004 880058671 881542936 882515135 882913100 883336104 883452723 883566027 884333453 884544136 884831855 884945470 885496415 886355307 886515170 886595318 887013299 887648542 887874489 889220902 889410047 890034190 890738903 891234382 892124787 892422799 892758318 894345627 895494397 896521710 896667686 896764354 897751278 898413530 899068713 899179511 899815655 901009306 901152513 901511282 902148038 902550915 902947606 903445196 903763901 904398747 904435483 905066174 905070756 905697009 906509594 906776984 907115895 907461940 907572273 908191425 908869520 909468025 909952739 910447538 910519253 910758450 911071881 911749539 911953762 912505670 914364593 914367554 914731678 914875556 915047397 916316517 917814720 918409048 919651136 919754597 920638251 921634107 921995977 922299249 922312831 922331793 922850865 923934354 924331194 924878450 925112052 925439121 926204626 926640147 926981724 927021859 927219513 927366847 927425096 928325702 929154903 930440248 930785108 930867782 931028759 931088379 931554680 931913072 933871486 933882873 933989007 934150421 935312364 936202563 936477251 936679784 937561857 937996894 939433331 940130372 940208748 940307801 940539264 940609258 940957820 940993892 941610417 942000923 942273911 942896133 943081970 944251826 944333355 944416917 946275052 946328825 947381591 949588919 949991083 951207614 951484236 951699800 951958546 952316053 952912328 953000842 954582724 954811940 955790330 955794113 955878748 955945685 956047764 957438811 957554721 958351279 960425923 960684375 960766331 961077767 962293440 963363144 963382303 963560825 964454664 964539977 964977046 965516108 965626619 965834430 966309211 966537192 967288421 967962682 968831011 972616399 973161360 973373548 973757848 975377380 975836267 975867023 976203832 976246064 976966292 977650936 977694986 977761648 977840283 978507518 978527135 978675851 980389867 980593074 980980500 981186920 981621584 982213353 982388817 983053901 983513032 983687695 983793763 984557059 985909195 986636481 987079005 988892527 989391229 989508957 989534825 989590969 990102158 990153012 991999168 992251050 992262709 992396543 992783309 994295305 994898500 995250270 996418459 996633932 999117143 999542367 999753016
610353699 1284 1345
1000000000 282 1557
737723255 484 1435
109373055 863 1597
618394100 1548 1573
988584680 1529 1685
808405368 337 628
88 1571 1731
1000000000 664 1174
318892543 1419 1512
260995894 900 1092
104030890 459 824
59 1352 1370
81406812 1027 1698
467252949 156 1643
1000000000 64 727
585072542 1040 1406
1000000000 630 1527
1000000000 770 1508
1000000000 405 789
608586547 1707 1727
970349675 1048 1064
1000000000 1015 1355
1000000000 294 574
1000000000 84 278
258255088 1029 1190
215272172 1369 1421
1000000000 1677 1681
272512917 1399 1432
642566382 886 1543
323962296 1642 1701
77047315 436 1480
957679616 1670 1683
1000000000 678 1461
823450845 991 1741
586173617 1638 1745
471505277 448 905
1000000000 852 1422
1000000000 1274 1722