1	1887145395
2	183646890
3	54160025
4	23747283
5	13061346
6	8715128
7	7234276
8	7431410
9	8974671
10	11478714
11	14516959
12	17806824
13	20824576
14	23015945
15	24373791
16	24926689
17	24655591
18	24127407
19	23724934
20	23980301
21	25166803
22	27625084
23	31386919
24	36228999
25	41803406
26	47819243
27	53721948
28	58876837
29	63067482
30	65854054
31	66800558
32	66165667
33	63784139
34	60108415
35	55169042
36	49512527
37	43469061
38	37425169
39	31634009
40	26289927
41	21542867
42	17457628
43	13965857
44	11087645
45	8794014
46	7024975
47	5689317
48	4740282
49	4064821
50	3587637
51	3273076
52	3095522
53	3006741
54	2968709
55	2984264
56	3009781
57	3058578
58	3104086
59	3156298
60	3188654
61	3198043
62	3190129
63	3158283
64	3113135
65	3043123
66	2944488
67	2831141
68	2702164
69	2555653
70	2416412
71	2268536
72	2115543
73	1967279
74	1832457
75	1700660
76	1582043
77	1482500
78	1393433
79	1310485
80	1246053
81	1193833
82	1147639
83	1111696
84	1081798
85	1061469
86	1046170
87	1029483
88	1015526
89	1007510
90	998249
91	993211
92	985653
93	972259
94	965176
95	953172
96	935461
97	919809
98	903443
99	884059
100	862153
101	836791
102	811273
103	783499
104	760000
105	733537
106	711775
107	690523
108	668213
109	643267
110	623177
111	608234
112	592974
113	574468
114	559993
115	551716
116	542138
117	531787
118	523946
119	518711
120	512608
121	504102
122	495381
123	489261
124	482968
125	475970
126	470754
127	464649
128	457410
129	452847
130	444616
131	438250
132	430274
133	421536
134	413410
135	406208
136	399280
137	390361
138	384127
139	376094
140	367315
141	360822
142	353757
143	346012
144	341753
145	335746
146	329996
147	323291
148	317217
149	313136
150	310886
151	306784
152	301929
153	299583
154	296007
155	290804
156	287101
157	283278
158	279366
159	276469
160	272269
161	268746
162	265601
163	263698
164	258976
165	257459
166	252883
167	248111
168	244023
169	242282
170	239430
171	235664
172	233386
173	229719
174	227037
175	224584
176	220520
177	216907
178	214097
179	212169
180	209008
181	207448
182	203126
183	202342
184	199016
185	197474
186	194580
187	193820
188	190459
189	188825
190	185189
191	183774
192	182735
193	179829
194	178066
195	176330
196	175241
197	172074
198	171126
199	168816
200	165923
201	164544
202	164213
203	162400
204	160755
205	157866
206	156548
207	154714
208	152955
209	151633
210	149071
211	149144
212	147656
213	146248
214	144164
215	141736
216	140584
217	139755
218	137737
219	137269
220	136064
221	134673
222	132849
223	131810
224	130959
225	129558
226	127839
227	127544
228	125576
229	124710
230	123385
231	121998
232	121489
233	120021
234	118607
235	117760
236	117380
237	116099
238	115097
239	113392
240	112603
241	111150
242	110686
243	109567
244	108882
245	107128
246	106437
247	106490
248	105391
249	103994
250	103212
251	102376
252	102725
253	100422
254	100155
255	99057
256	98119
257	97993
258	97057
259	96853
260	95035
261	94058
262	93547
263	93024
264	92026
265	90769
266	90412
267	90129
268	89054
269	88218
270	87424
271	86897
272	86288
273	85174
274	85026
275	84238
276	84003
277	83727
278	82349
279	82063
280	80981
281	80347
282	80266
283	79082
284	79029
285	78015
286	77143
287	76947
288	76542
289	76183
290	75900
291	75388
292	74194
293	74062
294	73589
295	73027
296	72528
297	71850
298	72021
299	70672
300	70480
301	69969
302	69644
303	69327
304	68476
305	67167
306	67008
307	66964
308	66829
309	66470
310	65633
311	65791
312	64707
313	64259
314	63792
315	63703
316	62949
317	62170
318	62253
319	61884
320	61789
321	61351
322	60621
323	61047
324	60438
325	60077
326	59662
327	58880
328	57987
329	58421
330	57818
331	57814
332	57246
333	57046
334	56986
335	56370
336	55362
337	55104
338	55215
339	54149
340	53598
341	53722
342	53748
343	52677
344	52907
345	52273
346	52178
347	51521
348	51719
349	51141
350	50569
351	50031
352	50841
353	49865
354	49730
355	49239
356	48955
357	48779
358	48174
359	48041
360	48117
361	47862
362	47695
363	47133
364	47147
365	46888
366	46746
367	46492
368	46352
369	45415
370	45553
371	45016
372	44725
373	44724
374	44663
375	44300
376	44439
377	43793
378	43676
379	42853
380	42876
381	42552
382	42588
383	42615
384	42394
385	41856
386	42059
387	41796
388	41523
389	40973
390	40313
391	40535
392	40537
393	40154
394	39991
395	40066
396	40030
397	39839
398	39205
399	38957
400	39027
401	38523
402	38673
403	38453
404	38341
405	37957
406	37566
407	37339
408	37365
409	36932
410	36884
411	36588
412	36566
413	36544
414	35972
415	36085
416	35738
417	35570
418	35760
419	35579
420	35725
421	35081
422	34781
423	34939
424	34088
425	34200
426	34423
427	33552
428	33943
429	33457
430	33456
431	33358
432	33649
433	33705
434	33283
435	32530
436	32350
437	32421
438	32046
439	31890
440	31943
441	32068
442	31464
443	31492
444	31557
445	30950
446	30943
447	30767
448	30989
449	30456
450	30592
451	30322
452	30155
453	30159
454	29800
455	30144
456	29688
457	29572
458	29187
459	29630
460	28774
461	28945
462	28649
463	28632
464	28723
465	28910
466	28210
467	28632
468	28265
469	28225
470	27991
471	27838
472	27747
473	27535
474	27487
475	27482
476	27478
477	27025
478	27207
479	27080
480	26813
481	26823
482	26529
483	26775
484	26278
485	26310
486	25755
487	25970
488	25415
489	25931
490	25740
491	25266
492	25167
493	25214
494	25259
495	24958
496	25135
497	24961
498	24967
499	24819
500	25040
501	24210
502	24441
503	24515
504	24134
505	24155
506	24013
507	23960
508	24196
509	23486
510	23544
511	23790
512	23570
513	23369
514	23582
515	23301
516	22996
517	23010
518	22757
519	23102
520	22836
521	22448
522	22358
523	22274
524	21956
525	22373
526	22561
527	21831
528	21980
529	21912
530	21992
531	21978
532	21562
533	21513
534	21599
535	21457
536	21435
537	21321
538	21292
539	21661
540	21046
541	21246
542	21128
543	20898
544	20681
545	20738
546	20772
547	20423
548	20145
549	20254
550	20220
551	20264
552	20320
553	20305
554	19807
555	19876
556	19697
557	19869
558	19345
559	19914
560	19626
561	19272
562	19651
563	19407
564	19406
565	19179
566	19182
567	18917
568	19296
569	19158
570	19094
571	18788
572	18918
573	18739
574	18553
575	18454
576	18396
577	18535
578	18394
579	18389
580	18536
581	18068
582	18384
583	17937
584	17762
585	17590
586	18054
587	18045
588	18123
589	17643
590	17760
591	17732
592	17158
593	17597
594	17293
595	17127
596	17251
597	17125
598	16921
599	16927
600	17200
601	17245
602	17214
603	16846
604	16873
605	16651
606	16631
607	16645
608	16519
609	16606
610	16325
611	16304
612	16307
613	16283
614	16302
615	16117
616	15886
617	15884
618	16015
619	15705
620	16246
621	15804
622	15670
623	15650
624	15500
625	15552
626	15412
627	15350
628	15349
629	15366
630	15518
631	15236
632	15474
633	15185
634	15184
635	15149
636	15137
637	14879
638	14767
639	14882
640	14716
641	14625
642	14691
643	14979
644	14812
645	14673
646	14515
647	14715
648	14538
649	14495
650	14564
651	14451
652	14371
653	14111
654	14417
655	14221
656	14010
657	14322
658	14217
659	14117
660	13941
661	13860
662	13806
663	13848
664	13584
665	13710
666	13785
667	13671
668	13589
669	13593
670	13711
671	13733
672	13144
673	13405
674	13191
675	13123
676	13029
677	13421
678	13179
679	13015
680	13026
681	12978
682	12953
683	12921
684	12827
685	13074
686	12726
687	12681
688	12564
689	12880
690	12880
691	12690
692	12454
693	12649
694	12802
695	12559
696	12565
697	12616
698	12521
699	12583
700	12459
701	12345
702	12585
703	12114
704	12122
705	12117
706	12041
707	12146
708	11990
709	12294
710	12079
711	11751
712	11862
713	11679
714	11991
715	11503
716	11906
717	11781
718	11782
719	11586
720	11527
721	11652
722	11484
723	11620
724	11521
725	11687
726	11299
727	11103
728	11211
729	10947
730	11360
731	11279
732	11162
733	10932
734	11008
735	11018
736	10987
737	11012
738	11047
739	10980
740	10878
741	10658
742	11084
743	11082
744	10722
745	10893
746	10840
747	10899
748	10559
749	10742
750	10715
751	10518
752	10567
753	10682
754	10321
755	10467
756	10471
757	10277
758	10224
759	10429
760	10460
761	10535
762	10378
763	10202
764	10375
765	10431
766	10172
767	10465
768	10246
769	10122
770	10334
771	9953
772	10056
773	10170
774	10133
775	9959
776	10063
777	10084
778	9773
779	10101
780	9983
781	9985
782	9805
783	9681
784	9824
785	9789
786	9800
787	9846
788	9886
789	9758
790	9783
791	9651
792	9622
793	9518
794	9356
795	9352
796	9663
797	9268
798	9350
799	9558
800	9465
801	9248
802	9306
803	9344
804	9433
805	9287
806	9346
807	9382
808	9199
809	9202
810	9279
811	9258
812	9339
813	9037
814	9064
815	9080
816	9038
817	9127
818	9009
819	9134
820	9065
821	8867
822	8734
823	8817
824	8929
825	8941
826	8763
827	8818
828	8753
829	8810
830	8955
831	8676
832	8769
833	8824
834	8665
835	8644
836	8812
837	8758
838	8661
839	8411
840	8592
841	8625
842	8294
843	8646
844	8443
845	8618
846	8602
847	8628
848	8538
849	8382
850	8479
851	8453
852	8293
853	8214
854	8112
855	8319
856	8311
857	8477
858	8336
859	8409
860	8208
861	8177
862	8280
863	8283
864	8090
865	8196
866	8100
867	8154
868	8255
869	8096
870	8098
871	7900
872	8108
873	7928
874	8105
875	8072
876	8143
877	7940
878	8069
879	8059
880	7930
881	7926
882	7762
883	7914
884	7858
885	7849
886	7762
887	7872
888	7992
889	7925
890	7892
891	7916
892	7954
893	7856
894	7808
895	7730
896	7858
897	7854
898	7579
899	7810
900	7855
901	7714
902	7879
903	7729
904	7852
905	7973
906	7855
907	7796
908	7858
909	7571
910	7698
911	7690
912	7657
913	7644
914	7618
915	7745
916	7740
917	7756
918	7633
919	7705
920	7710
921	7563
922	7671
923	7574
924	7536
925	7404
926	7611
927	7654
928	7663
929	7712
930	7432
931	7565
932	7545
933	7453
934	7571
935	7622
936	7712
937	7594
938	7406
939	7485
940	7472
941	7436
942	7388
943	7503
944	7487
945	7576
946	7501
947	7338
948	7523
949	7408
950	7434
951	7490
952	7433
953	7323
954	7482
955	7418
956	7308
957	7398
958	7500
959	7384
960	7319
961	7386
962	7151
963	7179
964	7333
965	7216
966	7029
967	7120
968	7033
969	7269
970	7115
971	7107
972	7085
973	7073
974	7234
975	7233
976	7058
977	7283
978	7122
979	7171
980	7027
981	6979
982	6926
983	6904
984	6961
985	7108
986	7100
987	6988
988	6993
989	6833
990	6940
991	6877
992	6831
993	6895
994	6765
995	6750
996	6756
997	6724
998	6828
999	6887
1000	21235489