1	682031598
2	54692873
3	26130732
4	26189123
5	32926298
6	41932408
7	51814796
8	61278323
9	68944351
10	73463817
11	74282422
12	71715457
13	66202944
14	58446554
15	49613710
16	40533621
17	32071478
18	24909240
19	19136240
20	14763358
21	11612135
22	9485510
23	8034029
24	7051058
25	6403818
26	5889253
27	5408676
28	4977944
29	4586360
30	4220158
31	3854613
32	3503432
33	3183354
34	2897334
35	2638387
36	2419937
37	2231446
38	2059979
39	1913446
40	1784617
41	1683108
42	1587817
43	1491764
44	1418325
45	1344419
46	1270000
47	1200910
48	1133966
49	1075597
50	1018474
51	969425
52	926286
53	885435
54	840830
55	800421
56	765561
57	740417
58	709297
59	685420
60	653441
61	630795
62	610245
63	585527
64	567079
65	544793
66	526893
67	506332
68	489135
69	475633
70	458118
71	445990
72	431259
73	416676
74	406847
75	393231
76	378304
77	369726
78	357557
79	347973
80	335579
81	328260
82	319210
83	312907
84	303313
85	295078
86	290243
87	282563
88	273410
89	264975
90	258525
91	251145
92	246838
93	239903
94	233769
95	230223
96	225547
97	220793
98	217323
99	210093
100	205532
101	201478
102	196508
103	192814
104	189643
105	185340
106	181038
107	177713
108	174372
109	170965
110	166365
111	164916
112	160794
113	159878
114	155655
115	151860
116	149913
117	146685
118	142432
119	139517
120	137596
121	134607
122	131534
123	129616
124	128030
125	126330
126	124251
127	121728
128	119455
129	116930
130	115173
131	113128
132	111295
133	110193
134	108227
135	106117
136	104075
137	102399
138	100545
139	99834
140	98008
141	97107
142	95192
143	93621
144	91784
145	90746
146	89861
147	88120
148	86813
149	85764
150	84418
151	83720
152	82514
153	81634
154	79565
155	78741
156	77199
157	76191
158	75194
159	74015
160	73149
161	72426
162	72028
163	70666
164	70024
165	68670
166	67935
167	66441
168	66599
169	65918
170	65000
171	64461
172	63239
173	62948
174	62464
175	60962
176	60248
177	59264
178	58666
179	57895
180	57195
181	56086
182	56031
183	55062
184	54284
185	53793
186	53814
187	52619
188	51478
189	51290
190	50555
191	50436
192	50078
193	49615
194	49071
195	48896
196	48048
197	47559
198	46782
199	45740
200	45498
201	45025
202	44605
203	44359
204	43937
205	43878
206	42462
207	42753
208	42448
209	41698
210	40840
211	40724
212	40704
213	40125
214	40281
215	39632
216	39186
217	39507
218	38770
219	38416
220	37800
221	37320
222	37344
223	37065
224	36477
225	36567
226	36245
227	36172
228	35160
229	35358
230	34347
231	34346
232	34003
233	33488
234	33542
235	33015
236	33170
237	32700
238	32422
239	32191
240	32336
241	31226
242	31503
243	30916
244	30829
245	30593
246	29867
247	29888
248	29737
249	29515
250	29679
251	29235
252	28600
253	28808
254	28228
255	28022
256	27707
257	27598
258	27583
259	27140
260	27137
261	27004
262	26989
263	26210
264	26411
265	25622
266	25934
267	25940
268	25287
269	24955
270	24709
271	24611
272	24489
273	24534
274	24276
275	24241
276	23994
277	24100
278	23382
279	23720
280	23623
281	22963
282	22695
283	22997
284	22615
285	22719
286	22314
287	22229
288	22057
289	22012
290	21891
291	21794
292	21301
293	21533
294	21071
295	21079
296	21257
297	20950
298	20507
299	20281
300	20082
301	20169
302	19985
303	20017
304	19894
305	19336
306	19756
307	19135
308	19274
309	19038
310	18944
311	18713
312	18921
313	18713
314	18602
315	18565
316	18430
317	18020
318	17938
319	17827
320	17863
321	17424
322	17914
323	17602
324	17458
325	17340
326	17275
327	16902
328	16825
329	16753
330	16823
331	16642
332	16478
333	16353
334	16397
335	16522
336	15991
337	16162
338	16134
339	16041
340	15538
341	15802
342	15824
343	15471
344	15492
345	15316
346	15328
347	15019
348	14952
349	14867
350	14708
351	14943
352	14546
353	14693
354	14453
355	14309
356	14463
357	14417
358	14465
359	14049
360	13932
361	13928
362	13944
363	13924
364	13526
365	13927
366	13661
367	13668
368	13540
369	13302
370	13291
371	13212
372	13295
373	13271
374	13112
375	12956
376	12810
377	13071
378	12901
379	13045
380	12879
381	12568
382	12582
383	12374
384	12318
385	12492
386	12475
387	12348
388	12033
389	12059
390	11940
391	12115
392	12021
393	11904
394	11888
395	11798
396	11843
397	11475
398	11439
399	11647
400	11661
401	11486
402	11314
403	11508
404	11419
405	11301
406	11366
407	11272
408	11095
409	11200
410	11067
411	10752
412	10689
413	10342
414	10728
415	10376
416	10651
417	10665
418	10461
419	10434
420	10487
421	10353
422	10144
423	9925
424	10106
425	10157
426	9941
427	10184
428	10156
429	9920
430	10002
431	9802
432	9738
433	9786
434	9836
435	9583
436	9583
437	9476
438	9588
439	9552
440	9354
441	9379
442	9520
443	9323
444	9283
445	9125
446	9340
447	9300
448	9075
449	8802
450	8942
451	9111
452	8838
453	8897
454	8932
455	8823
456	8680
457	8584
458	8622
459	8616
460	8677
461	8880
462	8573
463	8399
464	8656
465	8464
466	8330
467	8504
468	8555
469	8355
470	8266
471	8412
472	8243
473	8208
474	8210
475	8176
476	8274
477	8221
478	8087
479	8102
480	7776
481	7879
482	8041
483	7913
484	7950
485	7765
486	7973
487	7828
488	7709
489	7718
490	7878
491	7616
492	7465
493	7595
494	7570
495	7713
496	7566
497	7346
498	7351
499	7359
500	7320
501	7657
502	7329
503	7308
504	7274
505	7527
506	7316
507	7311
508	7013
509	7132
510	7084
511	7112
512	6967
513	6896
514	6887
515	6821
516	7048
517	6938
518	7059
519	7086
520	6791
521	6898
522	6770
523	6727
524	6704
525	6799
526	6646
527	6824
528	6677
529	6723
530	6713
531	6545
532	6632
533	6457
534	6379
535	6344
536	6520
537	6297
538	6209
539	6481
540	6490
541	6274
542	6354
543	6206
544	6056
545	6361
546	6164
547	6197
548	6126
549	5952
550	6078
551	6187
552	6126
553	6070
554	6034
555	6054
556	6029
557	5918
558	5944
559	5906
560	5836
561	5869
562	5857
563	5895
564	5910
565	5706
566	5948
567	5970
568	5817
569	5791
570	5766
571	5866
572	5668
573	5748
574	5765
575	5533
576	5552
577	5488
578	5415
579	5604
580	5474
581	5536
582	5459
583	5530
584	5395
585	5587
586	5544
587	5393
588	5274
589	5355
590	5379
591	5286
592	5234
593	5362
594	5260
595	5344
596	5306
597	5350
598	5239
599	5336
600	5112
601	5118
602	5207
603	5167
604	5050
605	5213
606	5190
607	5076
608	5097
609	4984
610	4991
611	4860
612	4873
613	5022
614	4966
615	4931
616	4751
617	4947
618	4802
619	4820
620	4864
621	4847
622	4684
623	4674
624	4920
625	4769
626	4796
627	4582
628	4676
629	4768
630	4847
631	4671
632	4666
633	4633
634	4621
635	4593
636	4482
637	4578
638	4569
639	4567
640	4507
641	4552
642	4574
643	4525
644	4464
645	4528
646	4403
647	4373
648	4303
649	4538
650	4409
651	4230
652	4387
653	4435
654	4301
655	4481
656	4368
657	4353
658	4331
659	4266
660	4255
661	4152
662	4232
663	4282
664	4381
665	4161
666	4164
667	4205
668	4023
669	4132
670	4156
671	4272
672	4098
673	4148
674	4110
675	4065
676	4117
677	4138
678	3968
679	4118
680	4037
681	4082
682	4168
683	4166
684	4069
685	3965
686	3880
687	4022
688	4102
689	4000
690	3946
691	4000
692	4045
693	4025
694	3835
695	3790
696	3860
697	3887
698	3924
699	3919
700	3780
701	3852
702	3970
703	3897
704	3737
705	3780
706	3859
707	3850
708	3870
709	3811
710	3940
711	3759
712	3774
713	3779
714	3676
715	3662
716	3668
717	3673
718	3667
719	3626
720	3757
721	3660
722	3625
723	3689
724	3625
725	3683
726	3716
727	3576
728	3405
729	3528
730	3548
731	3542
732	3523
733	3539
734	3466
735	3625
736	3456
737	3458
738	3526
739	3448
740	3492
741	3420
742	3400
743	3398
744	3440
745	3514
746	3434
747	3248
748	3489
749	3458
750	3399
751	3436
752	3330
753	3381
754	3283
755	3359
756	3361
757	3303
758	3309
759	3302
760	3346
761	3338
762	3216
763	3227
764	3236
765	3282
766	3233
767	3314
768	3227
769	3268
770	3070
771	3077
772	3226
773	3171
774	3183
775	3204
776	3232
777	3100
778	3079
779	3156
780	3093
781	3144
782	3095
783	3150
784	3162
785	3115
786	3076
787	3070
788	3232
789	3230
790	3163
791	3022
792	2996
793	3130
794	3052
795	3071
796	3105
797	2988
798	2961
799	2993
800	2963
801	3116
802	3049
803	2936
804	2922
805	3062
806	2969
807	2995
808	2793
809	2940
810	2891
811	2975
812	3010
813	2922
814	2927
815	2835
816	2835
817	2853
818	2804
819	2963
820	2879
821	2914
822	2824
823	2834
824	3002
825	2976
826	2829
827	2757
828	2837
829	2730
830	2832
831	2801
832	2923
833	2807
834	2792
835	2786
836	2736
837	2876
838	2863
839	2714
840	2842
841	2778
842	2745
843	2761
844	2683
845	2770
846	2803
847	2797
848	2664
849	2685
850	2795
851	2781
852	2678
853	2716
854	2655
855	2666
856	2755
857	2749
858	2649
859	2733
860	2733
861	2583
862	2665
863	2677
864	2627
865	2628
866	2709
867	2742
868	2630
869	2643
870	2715
871	2646
872	2701
873	2679
874	2644
875	2650
876	2595
877	2573
878	2502
879	2539
880	2609
881	2563
882	2518
883	2574
884	2623
885	2695
886	2628
887	2624
888	2662
889	2639
890	2610
891	2521
892	2541
893	2419
894	2441
895	2531
896	2467
897	2465
898	2371
899	2502
900	2573
901	2451
902	2516
903	2389
904	2440
905	2521
906	2487
907	2504
908	2449
909	2414
910	2392
911	2449
912	2345
913	2448
914	2378
915	2376
916	2388
917	2304
918	2302
919	2346
920	2282
921	2388
922	2416
923	2319
924	2300
925	2290
926	2268
927	2281
928	2253
929	2330
930	2270
931	2279
932	2318
933	2328
934	2257
935	2228
936	2201
937	2271
938	2309
939	2246
940	2303
941	2259
942	2269
943	2238
944	2124
945	2310
946	2243
947	2199
948	2204
949	2152
950	2155
951	2263
952	2123
953	2251
954	2137
955	2180
956	2141
957	2214
958	2223
959	2111
960	2224
961	2168
962	2219
963	2113
964	2134
965	2175
966	2209
967	2201
968	2133
969	2230
970	2187
971	2196
972	2166
973	2077
974	2108
975	2169
976	2087
977	2170
978	2134
979	2206
980	2190
981	2182
982	2049
983	2150
984	2061
985	2131
986	2090
987	2159
988	2166
989	2204
990	2078
991	2069
992	2130
993	2098
994	2112
995	2095
996	2019
997	2101
998	2115
999	2060
1000	11022896