1
900 10000
0 341946272
1 257056698
14 350744859
69 473468696
110 324541243
227 346414419
274 301301178
300 445670740
413 364877960
497 492132112
518 277685311
532 429352024
661 483467401
669 429739660
833 372953596
875 422643955
1001 239825569
1063 507808646
1097 215723592
1138 292661178
1223 353712467
1524 227224866
1531 416083955
1560 436312718
1616 341448752
1665 266782656
1746 450065384
1774 201746556
1789 201596556
1793 343000010
1896 341970010
2173 78867435
2228 237076541
2257 334454202
2463 217299118
2479 450513430
2506 212721051
2616 274624835
2700 349901707
2762 418289095
2770 450761627
2831 376256091
2849 279595827
2872 275321178
2903 226572307
2946 405212024
2963 363733864
2968 349269737
2991 537478790
3037 318314419
3051 406606909
3054 240712795
3061 109383757
3088 347634340
3170 260663938
3268 240490037
3288 224186698
3297 321731698
3400 239170037
3501 294379942
3517 334723248
3577 330651348
3653 502080994
3685 72979836
3746 279718461
3769 328252467
3802 303926272
3951 480214088
3953 211084495
4008 281775908
4038 69449836
4260 502662293
4266 272790320
4322 296335055
4472 205115569
4491 432131543
4536 333154340
4563 94363757
4572 204894495
4580 432661627
4584 368960217
4714 262767254
4715 139248083
4737 313149708
4770 365799867
4829 234575311
4834 425321326
4855 193379118
4896 327227644
5003 99224304
5012 200677654
5118 455092064
5128 407034793
5186 197975569
5190 424991778
5329 47307435
5412 458904696
5432 205036541
5442 148749785
5444 286788019
5490 267697609
5582 181961051
5625 265994206
5644 348386362
5682 306347455
5717 414520997
5724 272149942
5768 106950157
5787 422624615
5788 421040860
5860 205178994
5894 183524866
5900 41597435
5915 222176972
6011 416781778
6137 522078599
6322 190303968
6402 414441627
6447 290211615
6500 44829836
6529 408371326
6662 483594455
6705 351425616
6725 382356057
6762 429482112
6859 470020994
6901 287770675
6911 332809321
6937 223974788
6952 190434665
6979 190164665
7030 302509088
7072 184882307
7105 78204304
7141 125943955
7159 436864889
7232 210545311
7249 376180740
7271 370052951
7359 245609472
7408 471182293
7453 90100157
7462 221086889
7496 198826179
7511 305341318
7515 327477636
7654 366222951
7690 283619708
7717 241197380
7754 271038280
7836 221618305
7860 359077629
7870 452356431
7998 455584422
8010 213244788
8011 20487435
8040 455164422
8102 311669075
8114 320779321
8263 293557644
8328 282662467
8350 102957995
8422 257726272
8588 222751439
8694 53053757
8837 434462351
8867 212114835
8868 437994271
8920 313427636
9005 181202795
9020 59054304
9050 267880159
9101 179207381
9201 491438599
9259 184965317
9273 246381830
9283 382473430
9361 310956091
9427 248875187
9583 412624889
9631 196053938
9776 397981216
10041 436819641
10084 265102467
10224 295563576
10231 305752424
10272 274181707
10354 81693021
10382 289543864
10421 367480997
10501 92343955
10561 332067629
10569 323220028
10570 212667380
10652 242058280
10703 443184455
10727 429959641
10797 370950860
10833 404694696
10867 161967280
10919 340416057
10985 357675384
10998 209219472
11053 204920320
11117 321735957
11128 269171318
11301 334062775
11308 250087455
11330 157952795
11372 334950740
11395 415790492
11480 150150958
11511 325453279
11532 227825187
11540 415656431
11563 70827995
11649 173479939
11654 253353248
11696 222173392
11794 369018892
11798 283939321
11802 269484861
11813 223319351
11904 285526091
11976 403072351
11996 436196756
12016 172203938
12047 252339088
12082 179158305
12108 420472983
12140 120529118
12278 177983695
12306 103633592
12336 216195055
12361 274193576
12392 233104202
12399 294226538
12429 117639118
12433 230371698
12515 125647654
12615 335315851
12687 334595851
12707 266293864
12769 407406822
12807 238351348
12808 58318083
12825 98443592
12874 390984088
12889 311673279
12924 435894488
12934 227684202
12966 263029075
12971 364161644
13025 283249867
13134 138877381
13185 409702983
13219 226190159
13229 132660958
13384 434385152
13565 67519785
13831 335848696
13832 219288752
13876 202468019
13894 333394561
13933 240007189
13965 141676972
13970 46698083
14026 296856909
14041 336631543
14093 78107316
14219 384484271
14256 159820864
14259 140842656
14316 21470157
14368 374758646
14429 178307609
14437 40863021
14546 135866972
14558 353705885
14613 223763248
14653 182859942
14676 290356909
14686 418274488
14714 39317995
14751 148196889
14803 347711216
14841 386686822
14953 231753596
15016 417228790
15085 285579660
15121 197093307
15154 104062307
15193 279079367
15268 255382424
15281 249817636
15335 163828461
15373 251096362
15434 206590010
15555 144428305
15801 256713015
15908 370660492
15910 335451396
16031 298004793
16078 139198305
16087 178685055
16097 329107401
16198 97974665
16279 139590864
16352 251280217
16569 87833968
16647 184414859
16720 158627539
16725 181053307
16813 239932424
16845 208121203
16929 124054788
16958 232339321
17072 247496538
17099 71474866
17129 186318752
17208 327205885
17310 23845696
17381 29359785
17391 45127316
17481 84546541
17516 203789737
17519 331322909
17524 111254515
17537 203967189
17743 145729150
17795 7283021
17877 131137254
17896 315591396
17921 358031607
17939 388835152
17953 196657644
18018 228742948
18080 137567380
18103 127601439
18237 231129867
18260 82350958
18315 117613695
18369 372466756
18393 296564615
18433 131120320
18624 300718892
18638 64234495
18720 108506889
18758 349661607
18868 159898280
18904 282650997
18971 164991698
19013 63393968
19021 242695957
19130 130944206
19250 254572775
19256 253349095
19319 77447280
19335 163430675
19342 155264419
19355 28919843
19368 3673955
19370 211126362
19398 299891644
19412 257792718
19458 236429367
19485 284070860
19492 146529351
19584 277821326
19643 74207280
19671 184573596
19801 102774835
19850 262965851
19865 178251707
19918 277711778
19973 272604561
20038 276661543
20216 238403279
20328 211520217
20349 291061396
20378 115419472
20460 134511830
20511 237652951
20582 191966971
20627 157429809
20671 12327316
20720 306919538
20747 306649538
20755 239522775
20789 85454788
20844 129439519
20882 54958994
20884 188963576
20900 10486556
20942 28361051
20962 41177654
20963 166941203
21020 60017381
21024 268221627
21036 148020159
21126 145520675
21235 71082656
21245 136234419
21249 216420028
21620 352025152
21658 291874889
21698 91651439
21736 256301326
21855 256753430
21927 119841830
21933 159619737
21950 103659150
22019 188732948
22082 156114845
22107 100785908
22167 296768646
22232 34746698
22234 245185384
22268 125623307
22389 282382064
22443 211999660
22444 65529939
22511 206283955
22525 251641778
22703 356418599
22829 209387629
22843 88748461
22909 48465317
22985 108029519
22993 184793015
23052 95121243
23229 68473695
23244 213927821
23247 144464845
23319 121491615
23404 29738994
23405 124330159
23496 131461348
23639 79121442
23693 180744971
23698 276044696
23777 125929809
23804 180435616
23816 103289351
23820 275919538
23833 192679367
23864 148864861
23930 140037189
23956 123607455
24005 234108696
24009 99043392
24150 281332351
24154 32246179
24393 184980028
24446 134054340
24487 80957539
24624 134211318
24667 39824515
24698 129954845
24701 233484615
24800 238958892
24834 293212983
24860 281140492
24964 23530037
24967 185002024
24978 256492064
25128 166394971
25130 112399809
25157 99314859
25159 283974422
25180 32313444
25360 61911442
25427 48110864
25442 122151203
25443 67425908
25479 295424455
25494 276116431
25518 18606179
25584 250672909
25605 87095187
25631 190057821
25789 279339641
25891 18645317
25956 48525827
25994 100990010
26001 158206538
26005 246462909
26166 184707821
26433 74803392
26450 61327539
26522 50291442
26557 57027609
26763 231655885
26821 228892112
26995 220127401
27007 298155152
27029 71656272
27044 90079708
27104 137882948
27239 272872293
27252 120169075
27363 20106032
27366 141063015
27448 143194971
27585 173756057
27611 13859939
27742 30665827
27747 180844793
27765 32257254
27903 69273307
27961 61618019
28011 45531243
28117 191164561
28161 105894861
28185 274306756
28348 18529042
28353 283858790
28483 253780994
28600 494515
28635 128450217
28672 161950740
28762 145285957
28810 49779519
28811 35049150
28961 108176971
29011 86077644
29086 127615616
29099 63691615
29110 77907960
29126 292188599
29165 216804889
29221 203531216
29430 232374271
29534 241901607
29588 223844088
29621 155702718
29686 197011644
29735 148559095
29780 237296822
29787 74939088
29814 266994488
29816 27481243
29873 99056971
29952 22724206
29974 69267960
30050 17067344
30052 58055134
31431 36754683
31658 46362619
31800 217402565
32340 69876032
32722 37250061
33222 32241695
33882 96890882
34021 154976979
34184 78061006
35442 244590164
35567 105834431
35798 49894173
35993 219936243
35998 78653028
36334 80474689
36343 12545141
36630 2600191
36887 98232720
36965 28421981
37086 49004092
37220 71436305
37238 5958652
37241 49250850
37829 15122545
38059 130754431
38061 4038797
38813 168643444
39403 93245165
39421 156428949
39458 113253028
39529 26282040
39698 36049990
39873 79530528
40224 92332746
40338 144023459
40718 30992356
40888 158082346
41074 69511981
41077 31432811
41085 88605794
41449 112109136
41559 155635335
41698 23616136
41999 17362364
42071 50816752
42238 129035212
42440 221230215
42605 59628652
42669 53880912
42713 22303638
42754 135176062
43047 50018682
43208 131295165
43218 34376424
43257 77888385
43367 137963111
43482 73889990
43516 32532364
43617 136191695
43671 88131720
43749 67596752
43763 187015505
44234 11330633
44412 126941539
44426 102313728
44460 202670882
44487 67935155
44496 144196305
44510 167544683
44518 26704384
44667 120842461
44772 81777533
44888 11202371
45072 146678822
45135 2679260
45189 37089783
45246 6550905
45255 15433091
45315 3543943
45327 20364043
45413 22736045
45543 113483728
45563 145722746
45603 21357976
45622 99195798
45625 38033462
45690 113754813
45816 168190061
45843 79915660
45955 66860925
46091 63123029
46208 220150882
46229 86102356
46255 153918561
46351 114825581
46422 12307282
46573 316475696
46623 193059963
46741 18739260
46933 127383728
46958 54856985
47086 73056424
47166 92710263
47201 115229325
47313 118428302
47365 115269841
47392 125341720
47453 373932565
47514 365310164
47535 32587049
47585 95398682
47638 83016136
47719 154592391
47734 2036570
47748 30407225
47790 4238674
47946 124758302
48035 47444043
48061 76043909
48066 2198373
48179 9455439
48205 64375029
48279 35717225
48372 43156721
48476 55849972
48623 160588757
48624 13905439
48644 289086045
48725 6755385
48777 29455207
48841 42042179
48858 70905029
48970 22174616
49068 10185385
49107 14028457
49128 204785485
49139 306156979
49175 18088674
49201 87183638
49225 2172599
49263 14168373
49375 16858222
49383 22139003
49453 20868674
49464 16178373
49558 157700481
49621 2338356
49629 1738604
49655 2678356
49670 958784
49738 10421108
49777 60092371
49810 134932545
49854 2798784
49937 22478222
49948 194115
49977 121255660
50022 934115
50147 27311304
50169 24798222
50179 4687888
50193 4827888
50212 7568604
50289 15931108
50309 101170679
50324 110550925
50368 13602599
50399 164856608
50546 248393302
50550 103580679
50568 65116721
50596 27039140
50645 31146570
50724 967936
50817 120665139
50856 237307205
50872 251653302
50887 148350292
50946 226594689
50956 158675141
50992 3407091
51070 239447205
51173 53415207
51290 99400133
51313 209088822
51384 198328558
51415 316796045
51539 41231304
51561 128105139
51573 9457936
51589 7435111
51724 45549003
51783 11317091
51857 10115111
51981 117890679
52005 43008457
52063 6510462
52077 1045912
52104 42119140
52116 195518757
52137 75002179
52146 86787976
52228 91270633
52256 55034616
52320 86083091
52321 80447049
52326 61794149
52466 106443462
52495 88520340
52503 148095155
52590 128113029
52604 74127282
52608 169055798
52628 12160462
52715 14125304
52732 211869680
52765 161707533
52794 202112461
52835 235005212
52907 302376408
53119 85280905
53144 69974149
53280 174419841
53439 191244813
53612 86513943
53619 128127576
53625 16525912
53740 24375304
53741 160508293
53799 2425578
54026 191575581
54074 136173909
54084 18007649
54150 10443569
54152 271302619
54181 4568393
54198 133917576
54243 226918558
54272 12979508
54320 201750649
54437 25931354
54459 252226062
54478 175772040
54578 114386045
54607 27631354
54806 111630340
54847 362012005
54861 209498170
54978 11169006
55030 136800133
55081 171472811
55250 16935578
55408 177508797
55461 175660263
55546 207156693
55566 296303459
55601 14457017
55616 218280481
55658 19350359
55713 142329783
55867 23573178
55879 288152720
55970 150777052
56048 231090058
56081 37977649
56139 30333569
56362 134709972
56368 190870912
56489 256258561
56500 38325729
56609 202390191
56627 147794384
56729 311687693
56749 244892391
56813 228574945
56869 18475545
56919 261104173
56955 42875729
57473 274751695
57537 30107707
57608 161356985
57794 10551210
57799 291495485
57901 341228949
57909 197806404
58036 171437052
58182 258660850
58575 48520359
58661 229001248
58712 57379508
58926 50649006
59034 242036693
59535 58108393
59561 247306693
59738 238999841
59785 278650528
59943 64333178
60477 309063111
60520 239257533
60586 251178385
60629 225006404
60738 62117707
60755 51393244
61012 291752620
61033 288474092
61183 46695512
61263 71077017
61454 237638293
61457 46344848
61495 254430292
61611 239922356
61670 342913821
61825 261469325
61950 280366608
62042 298175794
62341 265801248
62719 288078170
63221 67075512
63519 534592565
63817 373219042
64085 299400649
64496 371789963
64667 79281210
64704 363607344
64743 63981401
64764 97425545
65278 426086408
65297 96813244
65357 314014945
65435 489719843
65631 469911917
66188 343512620
66191 521916243
66505 335660058
66661 98384848
67661 361159680
67904 492641917
68280 365621539
68857 120344848
69174 389359136
70319 439411006
70421 430423821
70541 502240215
70646 446505335
70815 457535505
70990 126451401
71279 129341401
71921 500172684
72251 466907693
73248 481682346
73366 491195134
75462 535582684
79901 612552005
