1000
198777828
514035278
914160520
415177210
556853084
331665462
130411850
485829588
732380736
241422092
127352840
743439046
138973580
517976874
367428620
855917394
413672556
855328670
818278188
336896224
495531520
893988596
834841288
303991702
701919442
715510076
907697800
686212592
205840898
668964044
741603800
264375900
380990568
334654732
970741306
888568482
40666580
358455514
351461724
231614300
90139378
766055672
553509456
268908506
832828288
212050946
253837662
99578188
39667344
960195280
349393660
983815064
986983796
778436610
571953168
849758416
172287822
803142260
425463408
967828226
818938948
883578594
762890646
555557326
186708672
242698158
199649526
691965982
325090680
745582946
171745826
518785342
496702202
846457418
115764558
438110600
192518196
45646866
363216402
353429292
122653486
245153820
192420804
557134576
86100744
454357306
565687552
539978018
767273590
282671860
233501632
586141958
871700816
460048536
16407822
500701282
801419976
474232450
547391602
878985160
943237518
592186944
282633884
120257752
363392802
802720312
415151050
246237480
80916214
701615618
409930718
640218528
186459260
670218976
576760920
164335354
971211802
398620772
241844476
813144232
762703354
338538904
108026156
417624412
742817044
671150650
769378154
418333988
479723300
18492876
755379890
667436658
39375678
593234072
910303122
227205630
845484422
578620762
716782632
313297450
400849498
473153772
399288528
67522566
640139930
177682334
898395012
840452998
908638778
774928446
500467470
973652834
474913640
509270808
840804320
252801784
552559062
871856082
489991594
62252958
183025814
284435062
236878664
359994438
531697580
873917196
427985600
121988820
550734126
770948462
514691394
526498156
588199328
435084550
970867622
954323246
491914334
319435292
109042574
905361156
570834328
28772538
671772036
989877294
318296934
92606408
453873124
920883158
658719862
393634312
881155592
551108420
600546196
311470996
329897672
801164160
69745336
505439698
640359054
495111538
754193026
605909448
534939000
994597120
297678638
526330586
210382364
534409868
783006096
708153906
849436494
642602412
334840594
66949170
495689024
985230004
202935266
692317480
710358368
189649944
785365710
223518984
69775578
144971412
312175790
442810698
316723620
320845098
375923850
577269278
926949774
330205802
803722090
586867770
637129216
242995410
622827734
342577416
206700510
851062500
492746454
558822632
190379996
752022380
707654610
469514270
803651034
750230874
772555594
23075288
956701352
508243268
505570214
671753008
287795818
595358568
674075142
212424012
819901084
139611570
744156892
42628968
495495896
420941778
687109732
63993238
167477896
850703212
389995942
312285598
991583840
842170734
519463362
354807812
558017854
186931056
28246810
754061704
204335834
390196260
683569220
105197542
652745054
590506560
568878416
754739654
446095986
779216240
212290764
164002578
821129472
178433516
9668238
85926376
337056254
469196756
716488742
231343494
199370806
757687252
691412424
131806184
494283788
650646788
874675172
546337794
445373784
827269388
3597700
334706094
120544182
784007626
491331338
494304938
6332344
212195572
580166114
403026364
283539550
338129326
241134024
515996580
970953976
827293916
956921988
199640136
719897646
340565822
469039458
660841726
639779728
252158116
233223274
455025288
849091098
145488406
633176570
257759086
830175410
145848382
248585774
54307750
445793340
791261990
983810184
924820108
692249538
887193714
738026814
468264682
128061050
182113724
545111698
861762838
868267490
246258620
676442524
466845762
684430648
999294996
158585532
300217654
307185452
998292044
414444924
603333776
521029876
727728820
12746892
941474668
561955798
732070536
444463392
122438012
668639966
319045672
148742494
48273350
665816774
999957162
383145742
922632700
544127288
583987624
756511686
279994872
978364822
333244346
468777014
197245342
978491726
887714230
738614968
477620148
538769312
211574938
226577302
690705124
496657088
783053342
904802202
908335194
893318084
717632852
440266670
562344006
353779004
473813618
474771358
455063756
636323168
482494302
437959858
405279708
202507518
380183668
466550688
146281414
129649796
973371614
888665426
361403138
699013492
410649316
841118598
352527604
99499284
86305056
866377982
676088390
654105930
664679350
961595622
680182236
314463240
684734364
152111104
307868012
484297306
716092564
216356752
119502124
630434414
5647018
865737818
982627340
431354678
269240144
725979392
691426846
852839322
516598330
689590286
165587670
134098028
516846596
304772914
482468142
93999614
653376454
738050868
157715776
23900756
845779192
95841916
820703904
348804538
707894914
376366362
855694816
864696112
39364148
58227828
751943274
635370000
332870850
603011040
227724308
769065776
121496916
179611950
889525108
213056748
435397184
589716890
10659338
223179610
984547304
136450574
201936086
537356424
649033700
257201298
51864410
944421304
472935786
487850434
380093062
21962800
122878174
86414024
826898662
858957404
584216058
578448262
182266850
303322864
337385166
218730852
170611792
489207446
240328408
259277430
61953314
82225742
465199932
192267950
80500416
230413424
838404076
961723848
845290622
680041422
950402906
266781738
447519144
166542904
549265074
23804652
398796052
340311094
582863320
515205446
307685398
200510706
944888698
870380014
234803022
684096862
912165804
889564576
694731326
730918386
240930160
592039046
542423670
906490830
862717456
614896578
1769052
416760144
254599374
191815144
406518310
362340274
8948248
232007654
460349126
74191874
469476436
232344378
306393530
769465784
607823122
303362580
398165176
754505952
396372412
666515496
102432556
766269702
963600856
987240372
799146100
620995200
402414554
934007296
641860878
437655950
596001674
715265406
952189350
696873360
980195854
571658730
952348824
320021126
754751500
663203570
376154066
386944766
739935540
792758674
643892288
978247448
275211438
557688124
351407116
718366880
106053374
426625478
787545012
733394424
973658798
509713670
204296262
311725938
172234340
600570152
109240182
630705044
495876388
133646178
771735142
48124158
329441014
775153798
490078636
704131956
973365556
11524258
563165520
119740916
422404040
494686520
699311308
345361892
456488440
768377522
795360086
500358290
396310732
855794482
809312092
82784550
369265144
44190812
684907250
23068858
211285648
173534128
615538240
977718800
41107204
16524148
753659454
49331230
403033200
850295638
711969444
243196796
171286790
917038864
362736106
862072760
722461900
35907958
816870736
715631302
311148532
741959452
681529176
463191986
991150182
353926010
374830792
185192062
369115276
693197012
60238116
6
291075456
305714174
979850592
99273422
985518826
757667206
476417890
176312970
973856456
487273554
203110804
704948040
147742652
975854402
233695514
228741844
861543476
105050472
381890230
544162872
932542668
463110062
676756904
436690632
509475796
371681468
748175062
873922376
871785672
589447064
11548930
438982432
182269226
767378836
910843880
604048678
990613888
671137520
89566630
903593946
581331832
351057094
757712804
648067708
756636004
16786762
539429944
553167604
244989354
992151598
926586896
726758252
689744922
482580762
508167522
210499124
558009620
724394134
456534238
133981046
871255300
551582944
997617030
479615502
985233744
399784876
52818362
736445412
198301790
488969866
352083304
677414760
564356828
93663820
652473880
397651788
489951812
430622842
956467562
129360648
150867308
441788710
952085108
707324374
873451274
924045662
315850068
677734546
549625438
650362676
373032270
973059040
120961658
461795662
352061012
104505492
86034138
279611208
357994604
762810702
497409778
79162412
369250642
491665464
310020176
686036074
895493504
947932944
260038936
864637052
653556204
543083382
967159878
194386088
986114976
450883378
899403072
37866596
654081828
366570508
411739846
824725888
215930658
838993384
583713760
705800328
136845462
613445590
699998080
215949508
564415526
920958636
371570668
661033860
526118600
490707490
472984626
272127802
181271690
446308548
401130860
901974644
641397916
179393290
427878242
826084436
5682098
618859920
853184722
709006124
633406452
79729150
269290778
451754654
290994560
10183248
308020774
956053376
930058066
153614766
470161350
814398348
909483256
601661566
464833216
563594956
632504784
673299374
404413308
644714488
910603944
782051658
422194408
973052664
905128306
732797286
751646590
547414574
209364484
546035202
698748824
717387286
98471266
528595436
361974146
343887626
782895226
764915902
999582332
573243450
221223652
914466618
348974824
392177842
590297682
597377258
577248660
670660830
868892124
949982614
498358452
77202482
255005366
673184236
420482176
310512176
192403066
56405604
440343306
607150820
235831206
196204592
490023338
804895608
355931028
817297830
705062042
311861020
700894400
442608468
686959306
981861066
751678998
630533206
858163690
21819992
655696070
422268278
50434502
536536774
525282336
199254
691437988
877446734
770833238
446476152
384023172
617861342
431587134
650187780
697877284
868057590
651696334
333809130
968304556
17170848
698271570
122785854
107917402
789721896
184272946
12694116
631964656
652663444
710113064
787858564
241839210
241876866
676645654
730392930
432477948
715779338
187421820
881343994
112452258
219799652
757557080
327628398
56348186
909540694
271061798
74861316
76241956
376206954
549967122
237765342
347984942
317335372
585571994
506402518
48696260
287393246
917174028
325148868
895938208
361967608
429022110
675164710
150280184
660782888
489828470
718843842
33037938
383898250
262692568
793724616
220978612
344410178
945420202
258343468
513177382
358084042
946528258
233719804
115719202
986018942
139860386
766304360
943735744
578572400
884369816
622509090
216724842
973344220
967974068
796264684
789502670
766565548
454658460
425977882
697996350
75430532
339720290
30678444
570191122
451659214
378455852
339036014
47182306