1	3008324266
2	157046634
3	51353459
4	28342116
5	21062003
6	19618145
7	21048378
8	23903855
9	27126636
10	29932185
11	31817929
12	32605171
13	32425974
14	31595310
15	30494413
16	29557015
17	29029838
18	29081337
19	29692200
20	30694671
21	31946669
22	33118544
23	33996737
24	34372219
25	34142617
26	33283818
27	31804565
28	29797410
29	27380116
30	24710794
31	21906829
32	19127326
33	16472440
34	14024116
35	11832862
36	9928116
37	8300627
38	6943824
39	5834752
40	4940992
41	4230160
42	3669909
43	3242804
44	2902782
45	2644092
46	2437987
47	2274337
48	2138619
49	2027322
50	1934961
51	1850266
52	1770512
53	1693946
54	1623771
55	1559154
56	1493911
57	1428547
58	1369617
59	1310161
60	1255903
61	1194798
62	1143089
63	1094914
64	1047342
65	1003741
66	962097
67	922879
68	888449
69	857607
70	826100
71	796204
72	771258
73	747863
74	723898
75	701866
76	679811
77	660829
78	639794
79	622825
80	605049
81	588541
82	573848
83	557343
84	542974
85	528660
86	515330
87	498718
88	484925
89	471961
90	458162
91	446738
92	436123
93	427292
94	414393
95	406186
96	396185
97	386408
98	377474
99	368707
100	359140
101	351844
102	344053
103	335802
104	328095
105	320238
106	314197
107	306821
108	301058
109	294604
110	287336
111	281713
112	277113
113	271550
114	267394
115	262281
116	256979
117	252353
118	246408
119	241897
120	237939
121	231565
122	228542
123	223238
124	219312
125	215583
126	212521
127	207734
128	205909
129	201191
130	197924
131	195005
132	190968
133	188010
134	185357
135	182535
136	179378
137	176883
138	174280
139	171533
140	168501
141	165156
142	162749
143	159383
144	157158
145	155278
146	153274
147	151423
148	149051
149	147981
150	144904
151	143525
152	141378
153	139212
154	137451
155	135514
156	133266
157	131299
158	129934
159	127026
160	126090
161	124434
162	122394
163	121382
164	119745
165	117103
166	116292
167	115266
168	113110
169	112135
170	110789
171	108911
172	107499
173	106300
174	105201
175	104538
176	102898
177	101775
178	100109
179	99181
180	97131
181	96672
182	95393
183	94420
184	93212
185	92110
186	91861
187	90307
188	89698
189	88172
190	87122
191	86025
192	84695
193	83742
194	83017
195	82153
196	81055
197	79505
198	79580
199	78289
200	77726
201	76723
202	75660
203	74669
204	74073
205	73077
206	72427
207	72319
208	71466
209	70009
210	69989
211	69007
212	68277
213	67484
214	67079
215	66663
216	65508
217	64819
218	64840
219	64259
220	63322
221	62484
222	62507
223	61571
224	60443
225	60110
226	59749
227	59150
228	58597
229	58164
230	57734
231	57612
232	57321
233	56478
234	55479
235	55406
236	54674
237	54774
238	54129
239	53748
240	52718
241	52910
242	52481
243	51328
244	51014
245	50744
246	51046
247	50003
248	50335
249	49400
250	48815
251	48509
252	48034
253	48149
254	47405
255	47365
256	46754
257	46218
258	46243
259	45720
260	45078
261	44690
262	44810
263	44798
264	44126
265	43848
266	43230
267	42860
268	42337
269	42139
270	41753
271	41799
272	41285
273	40872
274	40381
275	40313
276	40113
277	39616
278	39257
279	39111
280	38492
281	38525
282	38295
283	37780
284	36867
285	37411
286	37092
287	36952
288	36725
289	36966
290	36154
291	36089
292	35735
293	35911
294	35305
295	35256
296	34635
297	34780
298	34113
299	33933
300	33867
301	33820
302	33634
303	33298
304	33348
305	32837
306	32847
307	32641
308	32101
309	32125
310	32135
311	31518
312	31253
313	31267
314	30961
315	30905
316	30566
317	30659
318	30224
319	30097
320	29675
321	29450
322	29495
323	29358
324	29095
325	29020
326	28889
327	28501
328	28650
329	28450
330	28207
331	28165
332	27906
333	27851
334	27534
335	27216
336	26913
337	27141
338	26881
339	26688
340	26496
341	26311
342	26063
343	26261
344	25665
345	25714
346	25761
347	25366
348	25562
349	25555
350	24954
351	25355
352	24968
353	24710
354	24702
355	24721
356	24476
357	24548
358	24377
359	24220
360	24056
361	23787
362	23633
363	23480
364	23802
365	23346
366	23304
367	23031
368	23097
369	22750
370	22551
371	22583
372	22526
373	22474
374	22424
375	22225
376	22091
377	22101
378	22136
379	21938
380	21897
381	21731
382	21816
383	21602
384	21722
385	21424
386	21465
387	21107
388	20959
389	20902
390	20776
391	21056
392	20631
393	20662
394	20545
395	20298
396	20124
397	20354
398	20200
399	20015
400	19899
401	19822
402	19495
403	19811
404	19627
405	19573
406	19500
407	19187
408	19312
409	19139
410	19097
411	18950
412	18978
413	18764
414	18702
415	18343
416	18424
417	18295
418	18244
419	18376
420	18279
421	18163
422	18183
423	18100
424	18111
425	17980
426	18021
427	18050
428	18049
429	17804
430	17760
431	17878
432	17554
433	17478
434	17296
435	17260
436	17172
437	17419
438	17040
439	17077
440	16896
441	16870
442	16857
443	16781
444	16842
445	16680
446	16576
447	16493
448	16374
449	16151
450	16451
451	16152
452	16104
453	16134
454	15862
455	15912
456	15805
457	15713
458	15892
459	15373
460	15588
461	15094
462	15224
463	15341
464	15168
465	15342
466	15052
467	15196
468	15139
469	14976
470	14663
471	14667
472	14790
473	14685
474	14715
475	14400
476	14633
477	14823
478	14387
479	14134
480	14198
481	14023
482	14045
483	13992
484	14021
485	13839
486	13927
487	13643
488	13663
489	13771
490	13513
491	13576
492	13430
493	13180
494	13313
495	13342
496	13263
497	13040
498	13167
499	13003
500	13190
501	12799
502	12920
503	13051
504	12665
505	12730
506	12619
507	12689
508	12608
509	12655
510	12421
511	12378
512	12249
513	12251
514	12341
515	12093
516	12186
517	12166
518	12090
519	12105
520	12028
521	11871
522	11995
523	12034
524	11600
525	11762
526	11945
527	11577
528	11725
529	11585
530	11605
531	11438
532	11256
533	11210
534	11356
535	11209
536	11403
537	11058
538	11126
539	11106
540	10986
541	10935
542	10872
543	10901
544	11007
545	10909
546	11015
547	10729
548	10624
549	10651
550	10703
551	10533
552	10610
553	10683
554	10383
555	10393
556	10451
557	10384
558	10207
559	10197
560	10322
561	10116
562	10282
563	10187
564	10053
565	10062
566	10031
567	9909
568	9965
569	10070
570	9726
571	9832
572	9817
573	9892
574	9708
575	9791
576	9737
577	9582
578	9676
579	9462
580	9579
581	9558
582	9505
583	9387
584	9633
585	9415
586	9396
587	9519
588	9289
589	9166
590	9222
591	9245
592	9109
593	9298
594	9289
595	9145
596	9248
597	9015
598	9158
599	8997
600	8922
601	9067
602	8843
603	8846
604	8813
605	8850
606	8692
607	8845
608	8594
609	8641
610	8739
611	8836
612	8681
613	8446
614	8443
615	8553
616	8463
617	8625
618	8565
619	8507
620	8569
621	8413
622	8472
623	8095
624	8084
625	8085
626	8206
627	8154
628	8117
629	8197
630	7977
631	8054
632	8144
633	8040
634	8005
635	8043
636	7930
637	7906
638	7955
639	7955
640	7702
641	7865
642	7657
643	7756
644	7678
645	7783
646	7689
647	7519
648	7662
649	7628
650	7551
651	7442
652	7703
653	7561
654	7595
655	7556
656	7457
657	7452
658	7467
659	7417
660	7479
661	7362
662	7445
663	7599
664	7417
665	7358
666	7240
667	7274
668	7295
669	7376
670	7277
671	7154
672	7236
673	7180
674	6909
675	7146
676	7102
677	7084
678	6993
679	6944
680	6941
681	6907
682	6858
683	6881
684	6882
685	6830
686	6678
687	6962
688	6720
689	6782
690	6786
691	6846
692	6734
693	6866
694	6575
695	6714
696	6753
697	6621
698	6610
699	6583
700	6718
701	6666
702	6635
703	6458
704	6702
705	6499
706	6587
707	6487
708	6348
709	6474
710	6317
711	6462
712	6457
713	6495
714	6317
715	6245
716	6143
717	6363
718	6383
719	6226
720	6340
721	6205
722	6205
723	6219
724	6323
725	6197
726	6192
727	6158
728	6292
729	6164
730	6320
731	6118
732	6071
733	6041
734	6139
735	6061
736	6169
737	6009
738	6011
739	5950
740	6014
741	6048
742	5793
743	6011
744	6075
745	5811
746	5978
747	5993
748	5869
749	5904
750	5798
751	5983
752	5788
753	5901
754	5919
755	5612
756	5732
757	5804
758	5789
759	5854
760	5840
761	5727
762	5663
763	5782
764	5721
765	5568
766	5642
767	5643
768	5589
769	5569
770	5653
771	5689
772	5636
773	5611
774	5549
775	5748
776	5472
777	5512
778	5528
779	5595
780	5487
781	5600
782	5422
783	5416
784	5472
785	5474
786	5405
787	5330
788	5474
789	5462
790	5408
791	5426
792	5380
793	5232
794	5339
795	5299
796	5394
797	5381
798	5274
799	5359
800	5198
801	5338
802	5140
803	5257
804	5158
805	5109
806	5222
807	5242
808	4990
809	5163
810	5158
811	5150
812	5312
813	5168
814	5307
815	5133
816	5137
817	5252
818	5170
819	5049
820	5185
821	5108
822	5027
823	5082
824	5018
825	5176
826	5070
827	5076
828	5076
829	5050
830	5038
831	4946
832	4897
833	4937
834	4985
835	4942
836	4990
837	4971
838	5030
839	4950
840	4951
841	4852
842	4809
843	4906
844	4941
845	4841
846	4770
847	4822
848	4864
849	4882
850	4878
851	4671
852	4859
853	4840
854	4889
855	4831
856	4784
857	4782
858	4713
859	4718
860	4661
861	4763
862	4698
863	4705
864	4564
865	4759
866	4594
867	4593
868	4499
869	4442
870	4505
871	4517
872	4568
873	4560
874	4650
875	4550
876	4527
877	4479
878	4534
879	4423
880	4449
881	4381
882	4456
883	4475
884	4412
885	4460
886	4483
887	4353
888	4394
889	4423
890	4323
891	4357
892	4329
893	4363
894	4250
895	4440
896	4347
897	4264
898	4410
899	4245
900	4209
901	4294
902	4368
903	4315
904	4360
905	4145
906	4188
907	4098
908	4268
909	4144
910	4262
911	4258
912	4289
913	4209
914	4175
915	4108
916	4132
917	4182
918	4167
919	4113
920	4215
921	4188
922	4155
923	4112
924	4115
925	4149
926	4103
927	4075
928	4167
929	4130
930	4165
931	4191
932	4146
933	4083
934	4166
935	4089
936	4275
937	4154
938	4095
939	4168
940	4158
941	4247
942	4191
943	4136
944	4090
945	4081
946	4091
947	4021
948	4068
949	4101
950	3985
951	4015
952	4062
953	4025
954	3978
955	4073
956	3952
957	3937
958	3967
959	4026
960	3954
961	3907
962	3885
963	3959
964	3884
965	3876
966	3822
967	3899
968	3916
969	3796
970	3818
971	3811
972	3945
973	3720
974	3784
975	3708
976	3805
977	3772
978	3818
979	3874
980	3821
981	3739
982	3857
983	3894
984	3699
985	3794
986	3829
987	3802
988	3851
989	3731
990	3752
991	3771
992	3687
993	3603
994	3818
995	3798
996	3671
997	3885
998	3716
999	3680
1000	14874234