1	1192664062
2	181906209
3	66507178
4	33362686
5	19154483
6	11941912
7	7841975
8	5458092
9	3905428
10	2965927
11	2262311
12	1805094
13	1497624
14	1255790
15	1070581
16	947123
17	843740
18	746205
19	672029
20	589175
21	529928
22	477807
23	435858
24	404572
25	394476
26	402520
27	406140
28	414438
29	415512
30	408828
31	420058
32	420485
33	430822
34	437866
35	444542
36	434312
37	422772
38	421378
39	415479
40	414699
41	424455
42	437053
43	460007
44	489813
45	531745
46	584851
47	643003
48	715735
49	797051
50	886103
51	981642
52	1082210
53	1204221
54	1312801
55	1447060
56	1585944
57	1741819
58	1915813
59	2086415
60	2277543
61	2467376
62	2673840
63	2885454
64	3124416
65	3350477
66	3574758
67	3794549
68	4031628
69	4246622
70	4472021
71	4703121
72	4940233
73	5111397
74	5295175
75	5432658
76	5570467
77	5670473
78	5759503
79	5784794
80	5793282
81	5776811
82	5714796
83	5626656
84	5504902
85	5346917
86	5174936
87	4998604
88	4780987
89	4545901
90	4279706
91	4029754
92	3763838
93	3492665
94	3220066
95	2974842
96	2711749
97	2479396
98	2262233
99	2055444
100	1859346
101	1680094
102	1519143
103	1363411
104	1232700
105	1133718
106	1046353
107	978280
108	925627
109	880420
110	838845
111	815469
112	799574
113	802803
114	803372
115	821024
116	836698
117	870350
118	905392
119	944750
120	985556
121	1039120
122	1090271
123	1141584
124	1193111
125	1250260
126	1315849
127	1382153
128	1439895
129	1507418
130	1572156
131	1632305
132	1701308
133	1767836
134	1833516
135	1911654
136	1993198
137	2073580
138	2168108
139	2255142
140	2339277
141	2422921
142	2510537
143	2605677
144	2704193
145	2798244
146	2903840
147	2990220
148	3082476
149	3174265
150	3278517
151	3359134
152	3443820
153	3521283
154	3612768
155	3689633
156	3757721
157	3820787
158	3870472
159	3915078
160	3950965
161	3993052
162	4012529
163	4022095
164	4032529
165	4042821
166	4027782
167	4014014
168	3971332
169	3926682
170	3878113
171	3827532
172	3758171
173	3669829
174	3592643
175	3513455
176	3416995
177	3320758
178	3215446
179	3106258
180	3002276
181	2902064
182	2781399
183	2661549
184	2535285
185	2406029
186	2274256
187	2140228
188	2000269
189	1871754
190	1737702
191	1615248
192	1496792
193	1381079
194	1280612
195	1179564
196	1078951
197	991679
198	901097
199	818214
200	739327
201	667189
202	601969
203	541140
204	484021
205	435892
206	392490
207	350069
208	313487
209	282679
210	258883
211	233276
212	213063
213	192293
214	174861
215	157364
216	143164
217	131220
218	123009
219	114101
220	106904
221	101040
222	95452
223	90586
224	86071
225	82399
226	80147
227	77112
228	74663
229	73617
230	74586
231	73336
232	72845
233	72171
234	71834
235	73387
236	73906
237	74372
238	75229
239	75006
240	74128
241	74620
242	73928
243	73449
244	74212
245	73231
246	72090
247	71827
248	70110
249	70497
250	70360
251	70191
252	68043
253	67723
254	67315
255	65874
256	65045
257	65138
258	62888
259	62546
260	60195
261	59324
262	58861
263	57867
264	55893
265	55379
266	54636
267	53500
268	52300
269	50523
270	49540
271	49233
272	47564
273	46463
274	45687
275	44605
276	43150
277	43420
278	42721
279	42033
280	41395
281	40578
282	40642
283	40817
284	40031
285	39072
286	38985
287	39851
288	39405
289	38734
290	38990
291	39418
292	39548
293	39439
294	40298
295	40544
296	40550
297	40919
298	40405
299	41181
300	42397
301	42699
302	43425
303	43344
304	43329
305	43730
306	43367
307	44039
308	44776
309	45572
310	45181
311	46185
312	46621
313	46557
314	47000
315	47576
316	48160
317	48981
318	48910
319	48449
320	47808
321	48400
322	49026
323	48955
324	48501
325	49082
326	48755
327	49146
328	49113
329	48110
330	48773
331	48923
332	48659
333	48981
334	48279
335	47466
336	47206
337	47494
338	47635
339	46681
340	46516
341	45412
342	44334
343	43219
344	42981
345	42861
346	41585
347	41253
348	40011
349	39583
350	38035
351	37906
352	37352
353	35755
354	35987
355	35658
356	34458
357	33744
358	34135
359	33685
360	32879
361	32132
362	31287
363	30282
364	30048
365	29512
366	28768
367	28523
368	27987
369	26778
370	27008
371	26576
372	26589
373	25919
374	25168
375	24944
376	24500
377	23943
378	23193
379	22819
380	22429
381	22194
382	22071
383	22069
384	21411
385	21020
386	20854
387	20855
388	21129
389	21336
390	21326
391	20872
392	20997
393	20880
394	20735
395	21713
396	21197
397	20736
398	20792
399	21468
400	21512
401	21119
402	21485
403	21352
404	21358
405	21225
406	21866
407	21425
408	21163
409	21745
410	21476
411	21849
412	21468
413	21292
414	21594
415	20843
416	20614
417	20376
418	20397
419	20369
420	19718
421	19907
422	20160
423	19266
424	19556
425	19434
426	19393
427	19264
428	18775
429	18841
430	18695
431	18423
432	18004
433	17644
434	17421
435	17318
436	17601
437	17092
438	16943
439	17313
440	16760
441	16516
442	16550
443	16672
444	16674
445	16318
446	16602
447	16463
448	16538
449	16460
450	16704
451	15853
452	16451
453	16170
454	16783
455	16302
456	16563
457	16604
458	16206
459	16157
460	15923
461	15917
462	15990
463	15661
464	15614
465	15886
466	16082
467	15779
468	15650
469	15330
470	15690
471	15847
472	15395
473	14753
474	14677
475	15347
476	15687
477	15391
478	15424
479	15639
480	15253
481	16157
482	15628
483	15756
484	15586
485	15089
486	15007
487	15335
488	15371
489	15842
490	15735
491	15644
492	15556
493	15225
494	15054
495	14622
496	14730
497	14848
498	14090
499	14553
500	14818
501	14676
502	14509
503	14644
504	14545
505	14883
506	14664
507	14935
508	14450
509	14831
510	14507
511	14316
512	14185
513	13743
514	13894
515	13876
516	14127
517	13887
518	13956
519	14174
520	13891
521	13611
522	13829
523	13677
524	13718
525	13193
526	12752
527	12701
528	12899
529	12700
530	12458
531	11929
532	11915
533	11850
534	11798
535	11966
536	11807
537	11744
538	11514
539	11792
540	11721
541	11282
542	11272
543	11130
544	11271
545	10966
546	10948
547	11120
548	10776
549	10806
550	11099
551	11093
552	10924
553	10869
554	10861
555	10684
556	10755
557	10428
558	10374
559	10717
560	10455
561	10156
562	10179
563	9894
564	10045
565	10347
566	9899
567	9903
568	9911
569	9663
570	9614
571	9806
572	9577
573	9505
574	9530
575	9583
576	9487
577	9645
578	9526
579	9345
580	9628
581	9437
582	9363
583	9314
584	9431
585	9407
586	9437
587	9206
588	9228
589	9324
590	9107
591	9079
592	8971
593	8917
594	8999
595	9113
596	9263
597	9127
598	8803
599	8669
600	9113
601	8836
602	8880
603	9102
604	9138
605	9098
606	8833
607	8796
608	8717
609	8884
610	8868
611	8694
612	8557
613	8615
614	8399
615	8287
616	8395
617	8329
618	8312
619	8616
620	8542
621	8666
622	8691
623	8371
624	8304
625	8254
626	7834
627	8184
628	8428
629	8397
630	8132
631	8053
632	7895
633	7870
634	8091
635	7861
636	7902
637	7631
638	7647
639	7240
640	7197
641	7602
642	7579
643	7298
644	7581
645	7461
646	7453
647	7632
648	7559
649	7525
650	7280
651	7328
652	7401
653	7707
654	7324
655	7510
656	7371
657	7237
658	7506
659	7346
660	7416
661	7152
662	7245
663	7435
664	7372
665	7140
666	7202
667	7367
668	7158
669	7291
670	7222
671	7204
672	7043
673	7204
674	7330
675	7277
676	6987
677	7025
678	6920
679	6963
680	6968
681	7220
682	7145
683	7088
684	6848
685	6872
686	6548
687	6711
688	6709
689	6480
690	6529
691	6677
692	6555
693	6530
694	6476
695	6336
696	6466
697	6421
698	6337
699	6519
700	6309
701	6252
702	6405
703	6099
704	5997
705	6031
706	6188
707	6185
708	6064
709	6168
710	6218
711	6177
712	6009
713	5889
714	6006
715	5940
716	5883
717	5926
718	5975
719	5728
720	5818
721	5926
722	5869
723	5824
724	5850
725	5801
726	5975
727	5799
728	6036
729	5885
730	6041
731	5938
732	5748
733	5809
734	6027
735	5821
736	5814
737	5640
738	5808
739	5754
740	5740
741	5673
742	5390
743	5768
744	5778
745	5763
746	5473
747	5691
748	5942
749	5869
750	5865
751	5654
752	5693
753	5726
754	5614
755	5688
756	5675
757	5577
758	5521
759	5418
760	5494
761	5392
762	5184
763	5306
764	5100
765	5117
766	5100
767	5043
768	5259
769	5282
770	5152
771	5100
772	5068
773	4977
774	4903
775	4930
776	4835
777	4819
778	5067
779	4792
780	4756
781	4511
782	4662
783	4702
784	4655
785	4618
786	4765
787	4881
788	4881
789	4808
790	4706
791	4718
792	4747
793	4692
794	4771
795	4799
796	4641
797	4768
798	4701
799	4660
800	4893
801	4740
802	4745
803	4566
804	4678
805	4777
806	4693
807	4903
808	4809
809	4617
810	4679
811	4630
812	4702
813	4724
814	4504
815	4652
816	4644
817	4561
818	4685
819	4512
820	4576
821	4736
822	4924
823	4853
824	4598
825	4458
826	4558
827	4559
828	4620
829	4516
830	4619
831	4635
832	4634
833	4670
834	4417
835	4520
836	4633
837	4615
838	4721
839	4802
840	4633
841	4697
842	4520
843	4629
844	4665
845	4504
846	4383
847	4428
848	4486
849	4389
850	4267
851	4049
852	4060
853	4151
854	3904
855	4007
856	4013
857	4083
858	4126
859	3964
860	3868
861	4160
862	4048
863	4084
864	4136
865	4092
866	3964
867	3888
868	3932
869	3830
870	3830
871	3659
872	3743
873	3682
874	3701
875	3651
876	3471
877	3552
878	3646
879	3655
880	3618
881	3673
882	3667
883	3575
884	3636
885	3602
886	3554
887	3520
888	3492
889	3590
890	3659
891	3484
892	3583
893	3711
894	3665
895	3583
896	3599
897	3608
898	3533
899	3596
900	3499
901	3689
902	3707
903	3684
904	3755
905	3659
906	3794
907	3495
908	3610
909	3593
910	3534
911	3446
912	3542
913	3558
914	3636
915	3502
916	3447
917	3461
918	3371
919	3355
920	3383
921	3298
922	3314
923	3284
924	3252
925	3333
926	3520
927	3554
928	3364
929	3521
930	3403
931	3458
932	3303
933	3217
934	3201
935	3306
936	3248
937	3323
938	3262
939	3313
940	3313
941	3389
942	3206
943	3349
944	3235
945	3139
946	3199
947	3135
948	3222
949	3023
950	3147
951	3069
952	3171
953	3173
954	3286
955	3332
956	3316
957	3241
958	3201
959	2978
960	3118
961	3068
962	3184
963	3160
964	3139
965	3003
966	2936
967	2994
968	2930
969	2969
970	2838
971	3094
972	3041
973	3064
974	2895
975	3022
976	3065
977	3054
978	3001
979	3005
980	3047
981	3053
982	3103
983	2946
984	2967
985	2979
986	2920
987	3027
988	3121
989	2849
990	3071
991	2997
992	2871
993	2860
994	2921
995	2933
996	2857
997	2830
998	2781
999	2654
1000	12189156