1	3964
2	4054
3	4296
4	4225
5	4441
6	4564
7	4931
8	5277
9	5320
10	5078
11	4974
12	4673
13	4226
14	3630
15	3321
16	3459
17	3755
18	3986
19	3881
20	3520
21	3618
22	4338
23	5583
24	6755
25	7291
26	7003
27	6194
28	5431
29	5556
30	6304
31	7323
32	7416
33	6774
34	5480
35	4296
36	4000
37	3851
38	4008
39	4408
40	5259
41	6622
42	7597
43	7173
44	5816
45	5300
46	5056
47	5065
48	4944
49	5005
50	5017
51	5126
52	5121
53	4756
54	4646
55	5054
56	5946
57	6250
58	5238
59	3953
60	3520
61	3886
62	4771
63	5677
64	6284
65	6957
66	7592
67	7532
68	6815
69	5828
70	5003
71	4974
72	5385
73	5882
74	5984
75	5886
76	6025
77	6336
78	6787
79	7167
80	7248
81	6918
82	6795
83	6921
84	6968
85	6688
86	6374
87	5809
88	5794
89	5661
90	5685
91	5983
92	6472
93	7186
94	7344
95	7016
96	6770
97	6823
98	6367
99	5225
100	4259
101	3515
102	3406
103	3988
104	4639
105	5308
106	6371
107	7122
108	7308
109	7300
110	7543
111	7591
112	7441
113	7117
114	7225
115	7050
116	6746
117	5897
118	4883
119	4203
120	3972
121	4055
122	4453
123	4952
124	5452
125	6398
126	6577
127	6330
128	5761
129	5327
130	5254
131	5229
132	4894
133	4724
134	4622
135	4432
136	4768
137	4951
138	5353
139	5458
140	5441
141	5135
142	5354
143	5878
144	6417
145	6511
146	6146
147	5489
148	4942
149	5133
150	5603
151	5778
152	5314
153	4118
154	3646
155	3943
156	4669
157	4707
158	4247
159	3876
160	3689
161	3861
162	4027
163	4050
164	4264
165	4354
166	4404
167	4275
168	4303
169	3715
170	3128
171	2592
172	2766
173	3453
174	4430
175	5026
176	5347
177	5158
178	4986
179	4379
180	4035
181	4135
182	4709
183	5839
184	6730
185	6939
186	6919
187	6877
188	6946
189	7132
190	7114
191	6701
192	5897
193	5841
194	5312
195	5142
196	4813
197	5311
198	6291
199	8053
200	9334
201	9686
202	8735
203	7530
204	6102
205	5193
206	5473
207	6533
208	6989
209	6187
210	4533
211	3842
212	4169
213	5356
214	6306
215	6257
216	5776
217	5270
218	5716
219	6921
220	7825
221	7380
222	6657
223	6486
224	6201
225	6145
226	5876
227	5621
228	5523
229	5268
230	4601
231	3860
232	4091
233	5657
234	6887
235	7247
236	7243
237	6937
238	6630
239	6134
240	5333
241	4632
242	4692
243	5225
244	6072
245	7481
246	8486
247	8876
248	8590
249	8939
250	9116
251	8556
252	7331
253	6616
254	6400
255	5985
256	5580
257	6304
258	7479
259	7510
260	6340
261	5324
262	4924
263	5266
264	5964
265	6245
266	6216
267	5793
268	6556
269	7681
270	8784
271	9088
272	7572
273	5181
274	3639
275	3779
276	4792
277	6341
278	8049
279	8826
280	8249
281	7579
282	7009
283	6455
284	6518
285	6819
286	6935
287	6350
288	5144
289	4118
290	3923
291	4365
292	5693
293	7714
294	8591
295	8006
296	6969
297	6725
298	6782
299	6546
300	5551
301	4607
302	3809
303	4085
304	4846
305	5943
306	6620
307	6966
308	7086
309	6934
310	7377
311	7518
312	6626
313	5894
314	5423
315	5344
316	5065
317	5289
318	5893
319	5418
320	4710
321	4585
322	5051
323	5400
324	5679
325	5994
326	7193
327	9378
328	11109
329	10365
330	8246
331	7620
332	8587
333	8841
334	8159
335	7642
336	8060
337	9711
338	10443
339	9719
340	8279
341	7425
342	6962
343	6292
344	5278
345	5342
346	5684
347	5898
348	6953
349	8629
350	9881
351	9504
352	8652
353	8258
354	8329
355	7844
356	6955
357	7074
358	8126
359	8259
360	8082
361	8251
362	8685
363	8566
364	8116
365	7581
366	7241
367	6545
368	6070
369	5617
370	5721
371	6255
372	7734
373	10153
374	12154
375	12877
376	13453
377	13746
378	12909
379	11127
380	9138
381	6760
382	5421
383	5393
384	6821
385	8888
386	10325
387	9807
388	8719
389	8386
390	8862
391	8772
392	8461
393	9062
394	9457
395	9514
396	9691
397	10319
398	10482
399	9224
400	8034
401	7351
402	7525
403	8194
404	9953
405	11315
406	11727
407	10651
408	10306
409	11265
410	12572
411	12204
412	11087
413	9847
414	8242
415	6310
416	5826
417	7113
418	9363
419	11448
420	11086
421	9670
422	9027
423	9343
424	10564
425	12654
426	13629
427	11947
428	10029
429	10766
430	12428
431	12050
432	10098
433	9499
434	9453
435	9598
436	10023
437	10783
438	11180
439	10857
440	9389
441	8142
442	7908
443	8421
444	10353
445	12055
446	12798
447	12294
448	11676
449	11613
450	11410
451	11063
452	10436
453	9280
454	9346
455	9200
456	9442
457	10352
458	10895
459	10898
460	11117
461	12235
462	11809
463	10714
464	10573
465	11995
466	12574
467	11450
468	9655
469	9793
470	10413
471	11031
472	11821
473	12362
474	12182
475	12602
476	13619
477	13573
478	13377
479	13561
480	13534
481	13286
482	13664
483	14040
484	14167
485	13500
486	12813
487	12498
488	12199
489	11516
490	11756
491	13133
492	15073
493	17043
494	18811
495	19408
496	17864
497	16300
498	16266
499	16219
500	18614
501	21926
502	22906
503	21334
504	18328
505	15598
506	15862
507	18928
508	22562
509	25056
510	24037
511	19991
512	17751
513	17539
514	16447
515	15536
516	16326
517	16909
518	17690
519	18004
520	18394
521	18055
522	16805
523	16161
524	17647
525	20200
526	22745
527	23313
528	22804
529	22743
530	21485
531	18756
532	17625
533	18514
534	19663
535	20234
536	20729
537	22290
538	24670
539	24847
540	23376
541	22562
542	23689
543	25753
544	25509
545	23564
546	23202
547	25003
548	26509
549	26802
550	26263
551	25923
552	26228
553	25657
554	24527
555	26084
556	28172
557	30482
558	33009
559	34913
560	36240
561	34829
562	34121
563	34929
564	39509
565	42169
566	40993
567	40252
568	40759
569	41702
570	46961
571	54302
572	54318
573	46728
574	43157
575	45316
576	45576
577	41304
578	39735
579	43553
580	51400
581	56448
582	57150
583	59117
584	63854
585	66816
586	62795
587	60056
588	62912
589	66233
590	66111
591	67966
592	71055
593	74422
594	75978
595	74747
596	78427
597	85438
598	90488
599	94238
600	97185
601	97620
602	96235
603	99326
604	105530
605	105421
606	101654
607	101616
608	104156
609	105120
610	108574
611	118346
612	124056
613	123771
614	126115
615	128689
616	127628
617	129548
618	136834
619	145065
620	148517
621	155472
622	163613
623	169342
624	176934
625	184081
626	183967
627	189828
628	211887
629	225601
630	233608
631	242507
632	246203
633	242504
634	241536
635	240813
636	243904
637	254547
638	258971
639	254575
640	255961
641	263621
642	265919
643	270296
644	267455
645	264878
646	268424
647	270286
648	278082
649	280395
650	282944
651	286978
652	287484
653	291073
654	297637
655	288041
656	264642
657	252627
658	256565
659	251120
660	246035
661	249474
662	255592
663	248311
664	249733
665	265072
666	280235
667	277861
668	268908
669	269843
670	275199
671	276723
672	263892
673	246135
674	235607
675	228635
676	224409
677	215215
678	202558
679	198161
680	203333
681	201117
682	190744
683	179814
684	168663
685	158616
686	148204
687	137975
688	127248
689	129857
690	134764
691	129475
692	119647
693	115394
694	114255
695	116562
696	113858
697	102330
698	92871
699	82505
700	74116
701	73670
702	78416
703	82934
704	87310
705	84030
706	77840
707	69135
708	60539
709	56634
710	58397
711	61627
712	63568
713	63359
714	59943
715	60579
716	57880
717	54776
718	54298
719	51584
720	51848
721	52812
722	52815
723	47025
724	44389
725	44297
726	39769
727	38182
728	42489
729	46208
730	45167
731	45550
732	42269
733	38316
734	33870
735	31136
736	30125
737	29410
738	31915
739	37338
740	36242
741	33556
742	35121
743	31968
744	31274
745	32095
746	34103
747	31009
748	28027
749	29501
750	28138
751	27040
752	26783
753	26471
754	25349
755	22560
756	20337
757	20491
758	22466
759	27106
760	27055
761	23861
762	22788
763	23657
764	22609
765	23349
766	27552
767	27545
768	24458
769	23562
770	22589
771	20778
772	20719
773	20629
774	19781
775	19949
776	21770
777	23912
778	24990
779	26730
780	26482
781	22456
782	20188
783	18174
784	20601
785	20463
786	18581
787	18095
788	17391
789	18624
790	20827
791	20954
792	22834
793	20972
794	17576
795	14470
796	15926
797	18226
798	17278
799	14170
800	10618
801	12165
802	16523
803	18456
804	18068
805	17976
806	16125
807	13572
808	12304
809	12008
810	10157
811	9669
812	11789
813	13343
814	13852
815	14081
816	13666
817	12987
818	10781
819	12024
820	14265
821	13070
822	14107
823	18256
824	20092
825	17598
826	13709
827	13840
828	16688
829	16155
830	12419
831	10278
832	9839
833	8984
834	8425
835	9283
836	9335
837	9718
838	11926
839	11491
840	9991
841	8360
842	8467
843	7893
844	9605
845	10365
846	10163
847	11199
848	12829
849	12918
850	11129
851	10895
852	9798
853	9263
854	9499
855	9468
856	9198
857	8017
858	7329
859	7363
860	7669
861	8529
862	11193
863	11338
864	10330
865	11004
866	14214
867	10802
868	8189
869	8381
870	8040
871	9135
872	9169
873	8028
874	6609
875	7125
876	8722
877	11095
878	10961
879	8735
880	9323
881	8662
882	9192
883	9272
884	9098
885	7872
886	7751
887	7086
888	7502
889	8212
890	6083
891	5293
892	7179
893	9750
894	8391
895	6953
896	8872
897	8682
898	6054
899	6548
900	9096
901	9492
902	9433
903	9796
904	9594
905	7486
906	6412
907	6660
908	7760
909	7227
910	4957
911	4525
912	6075
913	6289
914	8359
915	9133
916	7483
917	7581
918	7495
919	7638
920	8534
921	8275
922	6311
923	4914
924	5002
925	6605
926	8821
927	8555
928	7695
929	6936
930	6173
931	7471
932	8093
933	7781
934	7763
935	8348
936	6866
937	8487
938	9889
939	9845
940	8967
941	7481
942	5210
943	5014
944	5011
945	4874
946	5465
947	6237
948	8578
949	9403
950	7577
951	4713
952	5388
953	5221
954	6020
955	7201
956	7327
957	5484
958	5138
959	5681
960	4696
961	3561
962	3024
963	2988
964	3457
965	3555
966	3355
967	4698
968	5375
969	5342
970	6326
971	7719
972	5666
973	3287
974	2520
975	2883
976	4465
977	5634
978	5776
979	6758
980	6898
981	3790
982	3785
983	5763
984	6246
985	5352
986	6412
987	8584
988	5892
989	6909
990	7533
991	5510
992	5823
993	5053
994	5136
995	5774
996	8221
997	9716
998	7569
999	4644
1000	3821
1001	5301
1002	7581
1003	9496
1004	6256
1005	4152
1006	4524
1007	7191
1008	7279
1009	7530
1010	6482
1011	4940
1012	4484
1013	5407
1014	5298
1015	3773
1016	4404
1017	5972
1018	6707
1019	5883
1020	5050
1021	5704
1022	5657
1023	4445
1024	2852