1	3161
2	2887
3	2416
4	2428
5	2641
6	2922
7	3281
8	3756
9	4171
10	4435
11	4447
12	4552
13	4491
14	4421
15	3927
16	3523
17	3915
18	4910
19	5535
20	5424
21	5015
22	4913
23	5078
24	5189
25	4809
26	4272
27	3968
28	3575
29	3241
30	2865
31	2848
32	2838
33	2895
34	2539
35	2176
36	2068
37	2169
38	2491
39	2918
40	3035
41	2921
42	2833
43	2500
44	2406
45	2594
46	2691
47	3209
48	3778
49	4468
50	4997
51	5482
52	5894
53	6352
54	6484
55	6333
56	6181
57	5834
58	5374
59	4964
60	5020
61	5033
62	5393
63	4933
64	4306
65	3527
66	3424
67	3494
68	3786
69	3861
70	3625
71	3492
72	3550
73	3774
74	4210
75	4409
76	4501
77	4870
78	5157
79	5088
80	4994
81	5045
82	5112
83	4981
84	4533
85	4130
86	3783
87	3968
88	4890
89	5566
90	5569
91	5185
92	4314
93	3874
94	3641
95	3522
96	3889
97	4391
98	4514
99	3920
100	3481
101	3499
102	3894
103	4135
104	3955
105	3400
106	2864
107	2293
108	1878
109	2005
110	2476
111	3104
112	3587
113	3418
114	3130
115	2738
116	2834
117	3154
118	3606
119	4012
120	4281
121	4614
122	4249
123	3844
124	3309
125	3363
126	3229
127	3166
128	3117
129	2939
130	3006
131	2792
132	2901
133	3276
134	3560
135	3713
136	3813
137	4226
138	4470
139	4640
140	4758
141	5219
142	5364
143	5374
144	5119
145	5041
146	5113
147	5126
148	4665
149	4228
150	3384
151	3015
152	3308
153	4094
154	4664
155	4646
156	4191
157	4120
158	4599
159	5655
160	6175
161	6157
162	5777
163	5105
164	5231
165	4977
166	4357
167	3918
168	3575
169	3374
170	3390
171	3551
172	4060
173	4422
174	4813
175	5131
176	5253
177	4739
178	4367
179	4328
180	4853
181	5363
182	5524
183	5340
184	5007
185	4763
186	4701
187	4752
188	4676
189	4274
190	3578
191	3365
192	3251
193	3368
194	3137
195	3020
196	2715
197	2867
198	3081
199	3372
200	3285
201	3086
202	2759
203	2507
204	2642
205	2686
206	2969
207	3623
208	4040
209	3996
210	3573
211	2969
212	2717
213	2907
214	3380
215	3862
216	3921
217	3813
218	4128
219	5092
220	5281
221	4864
222	3847
223	3356
224	3394
225	3782
226	4098
227	4213
228	4187
229	4286
230	4684
231	5185
232	4751
233	4050
234	3068
235	2502
236	2624
237	2857
238	3619
239	3745
240	4159
241	4283
242	4331
243	4527
244	4779
245	4507
246	4149
247	3607
248	3896
249	3623
250	3514
251	3564
252	4132
253	5071
254	5905
255	5854
256	4977
257	4273
258	4138
259	4786
260	5071
261	4948
262	4465
263	3845
264	3156
265	3062
266	3763
267	4657
268	5061
269	5639
270	6026
271	6117
272	5899
273	5386
274	4819
275	4553
276	4284
277	3778
278	3048
279	2828
280	3139
281	3955
282	4809
283	5009
284	5020
285	4949
286	4752
287	4823
288	4341
289	3968
290	3663
291	4047
292	4719
293	5003
294	4408
295	3389
296	2483
297	2670
298	3732
299	5150
300	5739
301	5680
302	5408
303	5048
304	4910
305	4570
306	4332
307	4285
308	4694
309	4752
310	4881
311	4350
312	3995
313	4332
314	4979
315	5581
316	6569
317	7552
318	7571
319	6793
320	6107
321	5957
322	6238
323	6852
324	7129
325	7518
326	7977
327	7880
328	6570
329	4757
330	3914
331	3860
332	4560
333	4891
334	4858
335	4866
336	4836
337	4446
338	4180
339	4647
340	5198
341	5807
342	6316
343	6073
344	5297
345	4408
346	3766
347	3786
348	4563
349	6493
350	7896
351	7613
352	5986
353	4810
354	4384
355	4117
356	3771
357	5032
358	6936
359	7599
360	6694
361	5212
362	4722
363	5046
364	4894
365	4703
366	4525
367	4685
368	4812
369	5233
370	5574
371	5284
372	4737
373	5198
374	5916
375	6655
376	6663
377	5284
378	4136
379	4292
380	5637
381	6392
382	6673
383	6556
384	6838
385	6910
386	6528
387	6236
388	6734
389	7343
390	7451
391	6750
392	5606
393	5313
394	5635
395	5814
396	5265
397	4684
398	4352
399	4338
400	5371
401	6984
402	7450
403	6522
404	6177
405	6147
406	5939
407	6022
408	6788
409	7313
410	8192
411	8100
412	7347
413	6626
414	6793
415	6898
416	7436
417	7072
418	6570
419	5988
420	5814
421	6741
422	7826
423	8113
424	8197
425	8123
426	8222
427	8671
428	9438
429	9389
430	9456
431	10110
432	10575
433	9826
434	6901
435	5086
436	4816
437	6392
438	8187
439	8770
440	8345
441	8695
442	8866
443	9008
444	8479
445	7203
446	6640
447	6360
448	6416
449	8977
450	12592
451	14509
452	13052
453	9653
454	7525
455	7326
456	7830
457	7882
458	7713
459	7219
460	6358
461	6675
462	7285
463	7462
464	7186
465	7000
466	7220
467	8019
468	8451
469	8530
470	7854
471	8224
472	8512
473	8628
474	9745
475	11579
476	12419
477	11422
478	11298
479	12460
480	13001
481	13049
482	12958
483	13036
484	13225
485	13187
486	12641
487	11812
488	10838
489	11029
490	11950
491	11596
492	9890
493	9669
494	11323
495	12778
496	11802
497	11386
498	13853
499	16736
500	17760
501	18053
502	17337
503	14529
504	12623
505	13950
506	16804
507	15922
508	12475
509	11510
510	14955
511	18548
512	16827
513	12588
514	10208
515	10208
516	12449
517	14412
518	15363
519	16693
520	17974
521	18195
522	18349
523	17859
524	16987
525	15975
526	15738
527	17941
528	20422
529	19414
530	16305
531	14178
532	13692
533	15405
534	16506
535	18424
536	19572
537	18695
538	18676
539	17959
540	17441
541	17256
542	16424
543	16441
544	18415
545	20913
546	23447
547	23826
548	24318
549	25611
550	24862
551	22886
552	22453
553	24911
554	28748
555	30519
556	30622
557	31202
558	31127
559	30419
560	30637
561	33069
562	32984
563	31406
564	33631
565	35242
566	33484
567	33803
568	37383
569	37215
570	36275
571	37190
572	35145
573	31373
574	33639
575	41138
576	45072
577	41993
578	41790
579	45834
580	53272
581	56415
582	54724
583	51420
584	46850
585	45904
586	47997
587	51918
588	57502
589	61671
590	64416
591	68008
592	66462
593	63784
594	66793
595	69596
596	75998
597	83071
598	87710
599	92869
600	92290
601	87200
602	84010
603	87066
604	89666
605	95018
606	109813
607	120344
608	119726
609	121756
610	130895
611	139263
612	145400
613	154857
614	164657
615	165602
616	156769
617	158296
618	168991
619	178271
620	187514
621	201333
622	221308
623	237954
624	248854
625	255650
626	271146
627	286970
628	315148
629	344779
630	367292
631	376666
632	375104
633	374129
634	384094
635	403367
636	427290
637	446761
638	455103
639	454117
640	448537
641	462816
642	469030
643	472326
644	473053
645	474721
646	480246
647	489159
648	514887
649	532654
650	543987
651	532823
652	503438
653	473762
654	465803
655	474542
656	471196
657	464799
658	455638
659	441039
660	449045
661	466009
662	470030
663	466563
664	473372
665	493100
666	503989
667	504437
668	507756
669	508654
670	508193
671	524202
672	546102
673	538585
674	510632
675	478401
676	459849
677	445421
678	425407
679	406513
680	387014
681	355090
682	328522
683	305312
684	282450
685	263669
686	248134
687	234294
688	216710
689	211719
690	206365
691	195902
692	179345
693	163363
694	162257
695	165138
696	159606
697	136879
698	119587
699	113307
700	114076
701	114075
702	110066
703	103648
704	97958
705	96019
706	96416
707	96090
708	91036
709	85605
710	75475
711	68908
712	68429
713	63543
714	57172
715	58473
716	63551
717	60072
718	58172
719	60138
720	58916
721	54404
722	51267
723	51953
724	56852
725	54983
726	51973
727	47536
728	44752
729	47914
730	48621
731	45275
732	41505
733	41579
734	43601
735	46814
736	46271
737	42555
738	38210
739	33847
740	31520
741	28461
742	29130
743	30309
744	32755
745	31861
746	29597
747	29065
748	29560
749	29408
750	28765
751	26711
752	25149
753	25088
754	21124
755	21115
756	23336
757	24056
758	23122
759	21428
760	20538
761	20623
762	21054
763	21245
764	20393
765	21633
766	22628
767	20017
768	17276
769	19381
770	25035
771	26863
772	23102
773	18900
774	16902
775	17444
776	16902
777	17339
778	19963
779	20358
780	19138
781	17470
782	16711
783	17687
784	18584
785	17938
786	18020
787	20862
788	18652
789	14007
790	10993
791	10084
792	10718
793	13605
794	12913
795	10926
796	12857
797	13308
798	11800
799	10487
800	10322
801	11612
802	13001
803	13975
804	14183
805	12342
806	10252
807	10500
808	9952
809	8062
810	7913
811	8651
812	10378
813	11648
814	10419
815	9646
816	8994
817	8371
818	8600
819	11406
820	11636
821	10282
822	7456
823	5496
824	5665
825	7975
826	9149
827	8919
828	7985
829	8015
830	9629
831	10304
832	8596
833	7842
834	7702
835	6323
836	6847
837	10409
838	12708
839	11062
840	8712
841	8740
842	8411
843	7329
844	7378
845	7234
846	7585
847	8895
848	8634
849	7730
850	6321
851	7385
852	8603
853	8860
854	10834
855	8628
856	7618
857	10222
858	8961
859	7492
860	7466
861	6984
862	7529
863	7148
864	7190
865	8345
866	7175
867	6797
868	5987
869	4895
870	5085
871	6057
872	7309
873	7110
874	4271
875	4437
876	4871
877	5632
878	6513
879	5836
880	5232
881	6400
882	5911
883	5516
884	6454
885	6710
886	7685
887	6124
888	4512
889	4878
890	6505
891	7672
892	7032
893	5039
894	7710
895	11647
896	9663
897	6941
898	6208
899	4899
900	6241
901	8444
902	6312
903	5205
904	7522
905	8710
906	7984
907	8066
908	7480
909	6477
910	5845
911	6396
912	7357
913	6788
914	4755
915	4176
916	4625
917	4202
918	3756
919	4818
920	4737
921	3371
922	2088
923	3111
924	4683
925	5359
926	5948
927	5100
928	5175
929	6824
930	10113
931	8993
932	7246
933	6430
934	5454
935	5210
936	6512
937	5924
938	5658
939	6035
940	4126
941	4626
942	5789
943	5177
944	4713
945	3228
946	3962
947	5157
948	5953
949	4023
950	3839
951	3660
952	2000
953	2974
954	3969
955	4466
956	4683
957	4805
958	3848
959	3726
960	5921
961	4678
962	4579
963	5021
964	5116
965	6002
966	4364
967	3024
968	2847
969	3354
970	4612
971	4143
972	4252
973	5844
974	5307
975	4368
976	4026
977	3719
978	3059
979	3947
980	3368
981	2964
982	2499
983	3045
984	4567
985	6962
986	6823
987	5842
988	3761
989	3043
990	2477
991	3755
992	4603
993	5875
994	5573
995	4662
996	6549
997	5685
998	3965
999	4613
1000	5749
1001	4823
1002	2250
1003	2578
1004	3216
1005	5010
1006	6636
1007	6277
1008	4766
1009	2961
1010	2082
1011	2214
1012	2999
1013	4018
1014	4460
1015	3045
1016	2211
1017	3082
1018	3750
1019	2963
1020	3710
1021	4867
1022	4229
1023	5986
1024	6037