1	3366
2	3262
3	3178
4	3168
5	3239
6	3405
7	3732
8	3771
9	3783
10	3782
11	3905
12	3988
13	4125
14	3840
15	3660
16	3160
17	2911
18	3021
19	3095
20	3332
21	3393
22	3457
23	3492
24	3752
25	4247
26	4193
27	4515
28	4434
29	4260
30	4130
31	4311
32	4363
33	4377
34	4291
35	4292
36	4134
37	4222
38	4017
39	4100
40	4273
41	4424
42	4266
43	4422
44	4181
45	4254
46	4309
47	4002
48	3906
49	3963
50	3900
51	4091
52	3755
53	3919
54	3956
55	4106
56	4159
57	4239
58	4179
59	4073
60	4205
61	4288
62	4344
63	4502
64	4385
65	4499
66	4702
67	4723
68	4695
69	4432
70	4459
71	4707
72	4790
73	4823
74	5039
75	5176
76	5288
77	5245
78	5261
79	5268
80	5480
81	5319
82	5347
83	5630
84	5909
85	6541
86	6679
87	6767
88	6691
89	6591
90	6778
91	6941
92	7191
93	7365
94	7674
95	8193
96	8747
97	9001
98	9480
99	10019
100	11104
101	12112
102	13282
103	14365
104	15141
105	16280
106	16764
107	17692
108	18943
109	20317
110	22335
111	24515
112	26767
113	29589
114	31972
115	34103
116	36163
117	38820
118	41048
119	42989
120	43950
121	44477
122	43659
123	42087
124	39880
125	37687
126	34516
127	31312
128	28407
129	25599
130	23654
131	21881
132	20330
133	18679
134	16820
135	15294
136	13989
137	13153
138	12567
139	11777
140	11372
141	10614
142	10334
143	10233
144	10381
145	10088
146	9236
147	8229
148	7721
149	7372
150	7371
151	7468
152	7405
153	7273
154	7084
155	6774
156	6413
157	6320
158	6300
159	6491
160	6722
161	6598
162	6390
163	5971
164	5759
165	5486
166	5292
167	5237
168	5072
169	5377
170	5591
171	5714
172	5576
173	5222
174	4913
175	4940
176	4937
177	4652
178	4548
179	4617
180	4575
181	4240
182	4145
183	4452
184	4893
185	5111
186	4837
187	4463
188	4263
189	4103
190	4239
191	4314
192	4216
193	4200
194	3979
195	4158
196	4040
197	3852
198	4125
199	4209
200	4461
201	4675
202	4733
203	4761
204	4555
205	4235
206	3836
207	3710
208	3896
209	3921
210	4171
211	4096
212	4279
213	4318
214	4461
215	4389
216	4272
217	4165
218	4267
219	4768
220	4982
221	4676
222	4233
223	3915
224	4068
225	4107
226	4135
227	4159
228	4241
229	4270
230	4296
231	3978
232	4047
233	4145
234	4112
235	4014
236	3937
237	4068
238	4356
239	4617
240	4577
241	4359
242	4257
243	3994
244	3818
245	3916
246	4263
247	4516
248	4508
249	4464
250	4309
251	4050
252	4077
253	3985
254	4039
255	3916
256	3864
257	3693
258	3660
259	4058
260	4190
261	4272
262	4512
263	4516
264	4181
265	3861
266	4143
267	4304
268	4605
269	4628
270	4257
271	4187
272	4355
273	4587
274	4759
275	4889
276	4961
277	4913
278	4919
279	5150
280	5381
281	5288
282	5342
283	5160
284	5070
285	5093
286	4932
287	5187
288	5335
289	5294
290	5438
291	5185
292	5171
293	5335
294	5344
295	5327
296	5346
297	5224
298	5037
299	5083
300	5098
301	4973
302	5304
303	5962
304	6895
305	7281
306	7439
307	7781
308	7853
309	8202
310	8111
311	7843
312	8379
313	9059
314	10083
315	10884
316	11216
317	11446
318	11432
319	12036
320	12698
321	13830
322	14570
323	15088
324	15041
325	15033
326	14948
327	14883
328	14746
329	14511
330	13781
331	12959
332	12159
333	11689
334	11067
335	10553
336	10310
337	10350
338	10556
339	10507
340	9859
341	9656
342	9642
343	9482
344	9974
345	10623
346	10903
347	10687
348	10844
349	11377
350	11827
351	11708
352	11130
353	10444
354	10517
355	10558
356	10730
357	10741
358	10772
359	10080
360	9291
361	8780
362	8684
363	8205
364	7626
365	7258
366	7167
367	7234
368	7282
369	6847
370	6708
371	6874
372	6656
373	6615
374	6840
375	7249
376	7544
377	7608
378	7184
379	6738
380	6706
381	7173
382	7398
383	7443
384	7391
385	7475
386	6939
387	6782
388	7312
389	7446
390	7349
391	7165
392	7129
393	6988
394	6670
395	6997
396	7747
397	8583
398	9216
399	9993
400	10363
401	10485
402	10441
403	10352
404	10308
405	9749
406	9674
407	9712
408	10237
409	10986
410	11636
411	11713
412	12141
413	12724
414	13751
415	14726
416	15436
417	15774
418	16591
419	17975
420	19450
421	19959
422	19289
423	19269
424	19308
425	19125
426	19044
427	18551
428	18117
429	17588
430	16433
431	15407
432	15004
433	14799
434	14548
435	14294
436	14190
437	14041
438	12908
439	12208
440	12626
441	12848
442	12626
443	12145
444	12362
445	12380
446	12886
447	12978
448	13199
449	13110
450	12836
451	13300
452	14289
453	14164
454	13970
455	14195
456	15037
457	15888
458	16492
459	17292
460	18113
461	19463
462	20484
463	22680
464	24885
465	26220
466	27424
467	28136
468	28983
469	30460
470	31214
471	32822
472	33487
473	34635
474	35183
475	36305
476	38682
477	41191
478	43536
479	45502
480	45971
481	46215
482	45837
483	46032
484	46950
485	46610
486	46649
487	46919
488	47204
489	46051
490	43674
491	42094
492	40951
493	40495
494	39567
495	40712
496	41441
497	40636
498	40942
499	40666
500	40848
501	41423
502	42503
503	43650
504	45329
505	47768
506	51178
507	53534
508	56796
509	60075
510	63668
511	66323
512	69211
513	73338
514	77940
515	81317
516	84154
517	85674
518	87382
519	88158
520	88641
521	85879
522	85830
523	88358
524	91999
525	95859
526	97549
527	100135
528	102757
529	107656
530	112707
531	118683
532	126247
533	132810
534	140642
535	150565
536	159821
537	166544
538	174440
539	180449
540	184934
541	189554
542	191245
543	186399
544	178933
545	171059
546	158784
547	146249
548	136137
549	128845
550	124964
551	121444
552	116510
553	109305
554	102275
555	96861
556	94449
557	94565
558	93424
559	91545
560	91694
561	92211
562	93334
563	93746
564	99060
565	103843
566	108408
567	114568
568	119463
569	120739
570	126385
571	135597
572	144527
573	152331
574	158972
575	168562
576	176928
577	183966
578	192086
579	198235
580	203390
581	204499
582	201788
583	194799
584	185641
585	178244
586	169775
587	163067
588	150547
589	135187
590	121928
591	114422
592	106904
593	97951
594	90669
595	82693
596	75748
597	70552
598	68440
599	64584
600	60865
601	57296
602	53584
603	50066
604	45745
605	42677
606	40458
607	38521
608	36375
609	34845
610	34116
611	34191
612	33272
613	32606
614	31862
615	30256
616	27623
617	26146
618	25195
619	25434
620	25607
621	25353
622	24504
623	23485
624	22936
625	23141
626	23003
627	23085
628	22808
629	23054
630	23877
631	23252
632	22563
633	23388
634	23658
635	23002
636	22682
637	22357
638	23063
639	23295
640	22551
641	23253
642	24648
643	26714
644	27996
645	30965
646	33951
647	35662
648	36445
649	36632
650	38500
651	38568
652	38792
653	40242
654	41148
655	41750
656	41421
657	40232
658	37209
659	35379
660	35284
661	33672
662	32407
663	30444
664	27943
665	26412
666	24716
667	23530
668	22047
669	20990
670	20277
671	19692
672	18518
673	17514
674	16925
675	15803
676	14524
677	14360
678	15138
679	15474
680	14450
681	14386
682	15058
683	15173
684	14689
685	14688
686	14109
687	13849
688	13803
689	13843
690	14415
691	14516
692	13989
693	12838
694	11999
695	11893
696	12189
697	11890
698	10905
699	10080
700	10240
701	10272
702	10228
703	10090
704	9586
705	8944
706	9552
707	9726
708	10154
709	10613
710	10433
711	9661
712	10017
713	10567
714	10177
715	10464
716	11498
717	11963
718	12277
719	12182
720	12946
721	12749
722	12887
723	12461
724	12840
725	12605
726	13437
727	13593
728	13980
729	14566
730	14650
731	14792
732	14388
733	13756
734	14179
735	13740
736	12674
737	12420
738	11140
739	9819
740	9665
741	9830
742	9761
743	8667
744	7776
745	7215
746	6992
747	7259
748	7606
749	7212
750	6885
751	7219
752	7831
753	7668
754	7048
755	6813
756	6429
757	6852
758	6915
759	6088
760	5306
761	5460
762	6140
763	5727
764	5569
765	5597
766	5024
767	4593
768	4793
769	4865
770	4798
771	4361
772	4366
773	4943
774	5557
775	5797
776	5462
777	5681
778	5569
779	5615
780	5652
781	4946
782	4699
783	4618
784	4611
785	4626
786	4469
787	4489
788	4991
789	5356
790	4956
791	4833
792	4968
793	5264
794	5331
795	4970
796	4100
797	4044
798	4226
799	4566
800	4024
801	3768
802	3485
803	3699
804	3756
805	3856
806	3789
807	3969
808	4195
809	4336
810	4265
811	4332
812	4314
813	4287
814	4345
815	4620
816	4861
817	4473
818	3852
819	4068
820	4788
821	5075
822	4589
823	3807
824	3511
825	3603
826	3780
827	4249
828	4435
829	4476
830	4069
831	4014
832	3780
833	3594
834	3823
835	3601
836	3036
837	3547
838	4036
839	4622
840	4719
841	4025
842	3995
843	3710
844	3822
845	4201
846	4207
847	3842
848	4556
849	4425
850	3640
851	3393
852	3570
853	4167
854	4263
855	3401
856	3116
857	2813
858	3132
859	3008
860	3336
861	3257
862	3018
863	2916
864	3388
865	4059
866	3758
867	3437
868	3408
869	4376
870	4578
871	4184
872	3602
873	3364
874	3617
875	3918
876	3871
877	4167
878	4563
879	4067
880	4038
881	3402
882	3235
883	3314
884	3303
885	3303
886	3431
887	3651
888	3683
889	3495
890	3491
891	3182
892	3148
893	3876
894	4314
895	4175
896	4399
897	3993
898	3672
899	3567
900	3503
901	3629
902	3818
903	3508
904	3834
905	3863
906	3525
907	3361
908	3536
909	3957
910	4169
911	3968
912	3535
913	3340
914	3586
915	3450
916	3229
917	3177
918	3155
919	3624
920	3828
921	4390
922	4421
923	3963
924	3472
925	3633
926	4136
927	4025
928	3632
929	3472
930	3021
931	2780
932	3153
933	3004
934	3063
935	3685
936	3785
937	3942
938	3520
939	2771
940	2515
941	3456
942	3664
943	3532
944	3924
945	3678
946	3414
947	2962
948	3383
949	3812
950	4154
951	4287
952	3780
953	2942
954	2739
955	2791
956	3503
957	3608
958	4052
959	3655
960	3702
961	4223
962	4739
963	4435
964	3702
965	2825
966	3020
967	3045
968	2989
969	3175
970	3273
971	3724
972	3552
973	3642
974	3118
975	2683
976	3224
977	3710
978	2950
979	2898
980	3269
981	3161
982	3127
983	3302
984	3616
985	3800
986	4019
987	4125
988	3862
989	3502
990	3301
991	3183
992	3262
993	3442
994	3321
995	3038
996	3160
997	3460
998	3559
999	3493
1000	3453
1001	3491
1002	3272
1003	3199
1004	3386
1005	4035
1006	4045
1007	4050
1008	4018
1009	3459
1010	3202
1011	2928
1012	3465
1013	3317
1014	2669
1015	2782
1016	3319
1017	3614
1018	3677
1019	4225
1020	3931
1021	3195
1022	2888
1023	3213
1024	3575