1	5944
2	7467
3	7896
4	7380
5	6020
6	4840
7	4313
8	4124
9	4280
10	4656
11	5279
12	5455
13	5081
14	4767
15	4096
16	3951
17	3755
18	3515
19	3211
20	2984
21	2983
22	3108
23	3481
24	4046
25	5300
26	6467
27	6929
28	6178
29	4918
30	3427
31	2959
32	2824
33	3173
34	3618
35	3989
36	4100
37	3574
38	2986
39	2460
40	2240
41	2160
42	2433
43	2505
44	2414
45	2616
46	3047
47	3323
48	3232
49	3129
50	3050
51	3278
52	3636
53	3795
54	3833
55	3687
56	3807
57	4150
58	4561
59	4834
60	5362
61	5619
62	5619
63	5218
64	4712
65	4461
66	4515
67	4346
68	4162
69	3841
70	3588
71	3367
72	3280
73	3620
74	4022
75	4391
76	4450
77	3985
78	3537
79	3369
80	3972
81	4494
82	4513
83	4135
84	3709
85	3481
86	3575
87	3660
88	3872
89	3497
90	3374
91	3476
92	3876
93	4802
94	5271
95	5184
96	4362
97	3359
98	2752
99	2728
100	3109
101	3729
102	3961
103	4055
104	4053
105	3585
106	3504
107	4182
108	5161
109	6130
110	6829
111	6785
112	6572
113	5628
114	4644
115	3385
116	2762
117	2944
118	3383
119	3378
120	2939
121	2098
122	1701
123	1696
124	1893
125	2321
126	3009
127	3303
128	3600
129	3727
130	4304
131	4978
132	5571
133	5800
134	5762
135	5442
136	4713
137	4177
138	3652
139	3299
140	3038
141	2657
142	2728
143	3366
144	4121
145	4896
146	4955
147	4879
148	4782
149	4537
150	4471
151	4516
152	4671
153	4450
154	4327
155	4174
156	4158
157	3987
158	3761
159	3567
160	3765
161	4513
162	5241
163	5570
164	5548
165	4979
166	4367
167	3457
168	2888
169	2565
170	2556
171	2542
172	2788
173	3122
174	3851
175	4287
176	4271
177	3401
178	3062
179	3334
180	4063
181	4148
182	3915
183	3626
184	3309
185	3191
186	3514
187	4022
188	4374
189	4302
190	4383
191	4982
192	5282
193	5933
194	6231
195	6004
196	5233
197	4578
198	4491
199	4608
200	4153
201	3201
202	2264
203	2304
204	3068
205	3973
206	4846
207	5177
208	5533
209	5796
210	6346
211	6580
212	6412
213	5959
214	5534
215	5425
216	5342
217	5564
218	5939
219	6258
220	6099
221	5498
222	4563
223	4188
224	4194
225	4481
226	4395
227	4512
228	4859
229	4789
230	4376
231	4230
232	4313
233	4689
234	4329
235	3654
236	3236
237	3516
238	3949
239	4085
240	4546
241	5002
242	5265
243	5094
244	5072
245	5475
246	6241
247	6475
248	6811
249	7266
250	7400
251	6953
252	6338
253	6218
254	6411
255	6428
256	6549
257	6604
258	6824
259	6847
260	6612
261	6412
262	6729
263	7766
264	8276
265	7617
266	6286
267	5040
268	4224
269	3908
270	4116
271	4108
272	3780
273	3100
274	2983
275	3824
276	5200
277	6109
278	6179
279	6183
280	6468
281	6572
282	6113
283	5560
284	5217
285	5212
286	5188
287	4944
288	3998
289	3884
290	4300
291	4927
292	4823
293	5382
294	6155
295	6464
296	6261
297	5670
298	4980
299	4324
300	3838
301	4268
302	4304
303	3975
304	3348
305	3500
306	4362
307	5580
308	6759
309	7614
310	8629
311	8649
312	6860
313	4652
314	3344
315	3451
316	3992
317	4444
318	4443
319	4531
320	5125
321	6554
322	7741
323	7589
324	7080
325	6956
326	7468
327	7200
328	6338
329	6527
330	7433
331	7244
332	6599
333	6073
334	6055
335	6203
336	6049
337	5346
338	5144
339	5357
340	5628
341	6100
342	6361
343	6809
344	7172
345	7909
346	8562
347	8926
348	8686
349	7597
350	5927
351	5328
352	5393
353	5626
354	6168
355	6877
356	7753
357	8588
358	8620
359	7828
360	7107
361	5949
362	5148
363	4832
364	5122
365	5184
366	4903
367	4830
368	5835
369	7501
370	9395
371	9743
372	8797
373	8700
374	9379
375	10616
376	10598
377	9167
378	6753
379	4916
380	5080
381	6367
382	8153
383	9964
384	10918
385	11695
386	12177
387	11712
388	10711
389	9124
390	8061
391	8046
392	8046
393	8220
394	8098
395	8865
396	9923
397	10229
398	9085
399	7741
400	7999
401	8556
402	7677
403	6400
404	5826
405	5447
406	5004
407	5079
408	5911
409	6703
410	7497
411	8462
412	8945
413	7913
414	7281
415	7196
416	7583
417	7646
418	7877
419	8684
420	9529
421	9383
422	8785
423	8086
424	7479
425	7870
426	8004
427	7052
428	5731
429	5365
430	6936
431	8781
432	9634
433	9370
434	7664
435	6900
436	7194
437	8110
438	8662
439	8408
440	8288
441	8884
442	9886
443	11344
444	13068
445	12511
446	11872
447	11506
448	10476
449	7775
450	5813
451	6367
452	8975
453	11503
454	11830
455	10347
456	8503
457	8167
458	9364
459	10023
460	9382
461	9146
462	9859
463	11396
464	11218
465	9676
466	9485
467	10002
468	9755
469	10186
470	9905
471	10189
472	11516
473	10997
474	8874
475	7928
476	8938
477	10208
478	11382
479	12091
480	12461
481	12125
482	13040
483	14355
484	15781
485	16007
486	14241
487	11185
488	9169
489	9736
490	12071
491	14696
492	16280
493	17942
494	18501
495	18302
496	17403
497	15874
498	15413
499	14006
500	12491
501	12552
502	14775
503	16928
504	18691
505	19213
506	19103
507	18336
508	16281
509	14504
510	14274
511	13521
512	12447
513	12676
514	13815
515	14655
516	15716
517	16375
518	16499
519	15966
520	15825
521	17121
522	17367
523	14342
524	12452
525	13991
526	15488
527	15482
528	17431
529	20024
530	20854
531	20427
532	18526
533	18472
534	19885
535	22695
536	25689
537	25480
538	23973
539	21029
540	18741
541	19879
542	22114
543	23841
544	24178
545	26412
546	27299
547	25522
548	24149
549	23507
550	24449
551	25018
552	25530
553	25716
554	24855
555	26608
556	29715
557	29321
558	26473
559	25993
560	26033
561	26470
562	29062
563	32624
564	35824
565	35322
566	33470
567	36269
568	42744
569	45647
570	44172
571	40974
572	38937
573	40609
574	41065
575	38999
576	38391
577	41035
578	43221
579	41501
580	40606
581	43937
582	50115
583	52471
584	52630
585	57150
586	60743
587	62136
588	63648
589	65119
590	62334
591	62257
592	63153
593	63512
594	63817
595	64223
596	67931
597	72954
598	77478
599	81127
600	83639
601	90356
602	94200
603	98238
604	103357
605	106525
606	108875
607	106930
608	110509
609	126069
610	136463
611	139904
612	143012
613	150339
614	158651
615	164555
616	166324
617	173035
618	184355
619	195949
620	193012
621	197638
622	220519
623	239416
624	243965
625	246765
626	267704
627	295055
628	319802
629	336197
630	350881
631	360060
632	377088
633	401910
634	422843
635	438541
636	443345
637	445901
638	448723
639	442284
640	437500
641	452229
642	461927
643	482653
644	492666
645	502795
646	522099
647	526202
648	524883
649	522895
650	516338
651	498094
652	485979
653	479520
654	480646
655	491580
656	474522
657	451121
658	434334
659	443409
660	468836
661	480462
662	484955
663	487726
664	490904
665	497942
666	499822
667	498691
668	504644
669	507515
670	512691
671	522334
672	524223
673	521975
674	521199
675	492454
676	454060
677	424661
678	410190
679	395802
680	374799
681	344749
682	319011
683	295988
684	278914
685	274423
686	267272
687	248354
688	219882
689	196759
690	184053
691	177772
692	173838
693	167834
694	154801
695	143000
696	140760
697	135502
698	124126
699	113946
700	110556
701	110304
702	107285
703	100279
704	93727
705	90770
706	87373
707	83665
708	84345
709	86283
710	83654
711	78291
712	73456
713	66646
714	65675
715	71320
716	66805
717	60660
718	60652
719	56784
720	52502
721	49906
722	50659
723	52091
724	55951
725	52496
726	47538
727	43118
728	44396
729	51653
730	54247
731	51738
732	46882
733	43905
734	38574
735	36572
736	35876
737	38119
738	44013
739	43051
740	35660
741	29621
742	28807
743	29396
744	30779
745	32819
746	32956
747	30214
748	27742
749	26579
750	25191
751	23084
752	21523
753	21535
754	23904
755	25625
756	27519
757	29010
758	23844
759	21377
760	21770
761	22989
762	24501
763	23670
764	20065
765	18547
766	18478
767	22501
768	22284
769	18123
770	16958
771	16809
772	16840
773	15938
774	16432
775	17733
776	18877
777	18443
778	16379
779	14476
780	14498
781	15388
782	16335
783	17030
784	20019
785	20434
786	17062
787	16504
788	16899
789	16194
790	13109
791	12581
792	12120
793	10996
794	10610
795	10939
796	11369
797	10445
798	11390
799	13228
800	13350
801	13069
802	14031
803	16662
804	16682
805	13846
806	11905
807	11314
808	10689
809	9790
810	10651
811	10562
812	8528
813	6193
814	6986
815	9945
816	11588
817	13226
818	10883
819	10541
820	13275
821	14224
822	13394
823	10122
824	9073
825	10312
826	10078
827	7970
828	5748
829	6646
830	8197
831	9609
832	9626
833	12720
834	13192
835	9172
836	7301
837	9066
838	8845
839	7499
840	8938
841	10875
842	11092
843	9516
844	7334
845	6145
846	5991
847	7103
848	7274
849	6456
850	7492
851	7990
852	7577
853	7448
854	8781
855	11156
856	10526
857	6557
858	6077
859	6380
860	7638
861	7376
862	5725
863	7095
864	9149
865	8445
866	5195
867	6251
868	8702
869	8221
870	6360
871	8594
872	10315
873	9113
874	7796
875	6595
876	6088
877	6137
878	5394
879	3907
880	3523
881	4945
882	5511
883	5554
884	6685
885	7119
886	7701
887	7611
888	6046
889	5073
890	5799
891	6290
892	7666
893	8269
894	7335
895	6611
896	7961
897	7998
898	6492
899	6249
900	4917
901	4959
902	6185
903	5592
904	6580
905	6408
906	4669
907	3512
908	4801
909	6560
910	7257
911	5861
912	4336
913	4019
914	3949
915	7117
916	8952
917	6159
918	6309
919	7482
920	6571
921	6897
922	7322
923	7985
924	8013
925	5389
926	5014
927	6060
928	5346
929	5461
930	6304
931	6033
932	5223
933	4655
934	2836
935	3556
936	4721
937	3699
938	5870
939	5503
940	4684
941	4862
942	4858
943	6664
944	9738
945	8381
946	6733
947	6511
948	6348
949	5285
950	6388
951	6551
952	4151
953	2474
954	2609
955	2918
956	2901
957	3297
958	3989
959	5290
960	4029
961	4273
962	6407
963	5310
964	4175
965	3690
966	3973
967	4093
968	5035
969	3963
970	3345
971	4388
972	3160
973	3901
974	5647
975	5477
976	5430
977	6846
978	6586
979	4488
980	4653
981	4363
982	2961
983	4297
984	6294
985	4827
986	3939
987	4303
988	3919
989	3486
990	3751
991	4851
992	3838
993	2877
994	5039
995	5629
996	4786
997	6235
998	4999
999	4257
1000	4135
1001	3531
1002	3616
1003	5830
1004	5686
1005	4554
1006	4363
1007	4619
1008	4075
1009	4218
1010	3880
1011	3689
1012	4690
1013	5915
1014	7673
1015	7833
1016	7025
1017	5704
1018	6241
1019	6074
1020	6626
1021	4321
1022	2787
1023	2582
1024	4010