1	3778
2	4153
3	4143
4	4062
5	4076
6	4091
7	4291
8	4569
9	4523
10	4114
11	3757
12	3203
13	3131
14	3234
15	3081
16	2978
17	2922
18	3201
19	3633
20	3747
21	3646
22	3327
23	2791
24	2778
25	3329
26	4427
27	5298
28	5858
29	5696
30	5325
31	4570
32	3879
33	3568
34	3618
35	3667
36	3887
37	3921
38	4312
39	4568
40	4740
41	4493
42	4012
43	3682
44	3536
45	3931
46	4053
47	4173
48	4440
49	4584
50	4221
51	3762
52	3249
53	3233
54	3760
55	4208
56	4610
57	4818
58	4902
59	4550
60	3931
61	2926
62	2499
63	2338
64	3242
65	4138
66	4866
67	4776
68	4139
69	3438
70	3259
71	3749
72	4182
73	4252
74	3736
75	3058
76	2851
77	3190
78	3634
79	4006
80	4199
81	4249
82	4140
83	3982
84	3867
85	3953
86	4251
87	4265
88	4128
89	4034
90	4513
91	5097
92	5075
93	4689
94	4163
95	3604
96	3064
97	3292
98	3477
99	4162
100	4805
101	5088
102	5096
103	5098
104	4572
105	3883
106	3330
107	2990
108	2698
109	2158
110	1834
111	2032
112	3022
113	3710
114	4573
115	4940
116	5481
117	6141
118	6619
119	5910
120	4622
121	3316
122	2939
123	3139
124	3356
125	3947
126	4402
127	4685
128	4875
129	5193
130	5712
131	5947
132	5734
133	5034
134	4083
135	3054
136	2693
137	2579
138	2922
139	3344
140	3409
141	3286
142	3176
143	3273
144	3299
145	3542
146	3840
147	3829
148	3799
149	3504
150	3292
151	3385
152	3672
153	3461
154	3283
155	3198
156	3582
157	3787
158	4125
159	4492
160	4574
161	4415
162	3859
163	3201
164	3079
165	3121
166	3104
167	2893
168	3180
169	3515
170	3979
171	4068
172	4014
173	3944
174	4488
175	5337
176	6105
177	6257
178	6548
179	6906
180	6652
181	5373
182	4214
183	4065
184	4321
185	5079
186	5428
187	5305
188	4384
189	3028
190	1931
191	1741
192	2404
193	4080
194	5177
195	5124
196	3572
197	2239
198	1768
199	2492
200	3728
201	5017
202	5348
203	4588
204	3791
205	3096
206	3142
207	3105
208	2869
209	3067
210	3555
211	4466
212	5394
213	5733
214	5563
215	5292
216	5304
217	5085
218	4605
219	4017
220	4056
221	4179
222	4534
223	5100
224	5660
225	5335
226	4603
227	4247
228	3850
229	3427
230	2881
231	2879
232	3417
233	4470
234	5309
235	5584
236	6384
237	7038
238	6985
239	5703
240	4971
241	4670
242	4803
243	4513
244	4057
245	3708
246	3800
247	3970
248	4529
249	4998
250	5176
251	5116
252	5055
253	5110
254	4960
255	4262
256	3955
257	4332
258	4329
259	3904
260	3646
261	4249
262	4887
263	5520
264	5575
265	5625
266	6190
267	6759
268	7005
269	5872
270	4104
271	3317
272	3392
273	3753
274	4023
275	4200
276	4145
277	3757
278	3277
279	3382
280	4559
281	5979
282	6544
283	6657
284	6574
285	6554
286	6854
287	7448
288	7895
289	7516
290	6330
291	5705
292	5443
293	5632
294	5863
295	5964
296	5514
297	4509
298	3815
299	4068
300	4242
301	4321
302	4599
303	5292
304	5672
305	5314
306	4968
307	5332
308	6687
309	8071
310	8027
311	6669
312	4811
313	3804
314	3943
315	4650
316	4975
317	5900
318	6548
319	6804
320	6766
321	8279
322	10504
323	11736
324	10101
325	7195
326	5320
327	5095
328	5500
329	5614
330	5887
331	5829
332	5451
333	5040
334	5204
335	5365
336	4717
337	4199
338	3671
339	3937
340	4450
341	5068
342	5734
343	5948
344	5234
345	4648
346	4193
347	3488
348	2966
349	3076
350	3754
351	4611
352	5945
353	7434
354	8006
355	7067
356	6130
357	5662
358	5557
359	5483
360	5528
361	4742
362	3813
363	3766
364	4337
365	4759
366	5576
367	6069
368	5975
369	5089
370	4049
371	4130
372	5021
373	5521
374	5380
375	4906
376	5092
377	5226
378	5053
379	4344
380	3845
381	3562
382	3476
383	3388
384	3279
385	3785
386	4420
387	5812
388	6860
389	7064
390	5982
391	4962
392	4224
393	4401
394	4577
395	5234
396	5689
397	6116
398	6543
399	5765
400	5610
401	6431
402	8045
403	9097
404	8542
405	7399
406	6978
407	6722
408	6947
409	7928
410	8840
411	8268
412	7925
413	7738
414	8116
415	8840
416	9543
417	8892
418	7877
419	6728
420	5631
421	5425
422	6915
423	9706
424	11498
425	11053
426	9537
427	7744
428	7238
429	7435
430	7858
431	8323
432	7848
433	7363
434	6547
435	6165
436	6188
437	7325
438	7706
439	7020
440	6992
441	7659
442	8947
443	9302
444	8688
445	7690
446	7323
447	6770
448	5965
449	6081
450	7020
451	8088
452	9901
453	10893
454	10541
455	9947
456	10031
457	10188
458	9012
459	8264
460	8056
461	8127
462	8438
463	8026
464	6869
465	5795
466	5661
467	7025
468	8596
469	9802
470	10190
471	10832
472	11106
473	10552
474	11546
475	12162
476	11245
477	10200
478	10001
479	9386
480	8705
481	9534
482	10800
483	11664
484	13858
485	16877
486	17762
487	16145
488	15063
489	14729
490	15014
491	15036
492	14725
493	15067
494	15392
495	14249
496	11011
497	8762
498	9039
499	9641
500	10379
501	12324
502	13679
503	13964
504	13412
505	11793
506	10700
507	11132
508	12323
509	12705
510	12959
511	13783
512	15423
513	15887
514	15063
515	14417
516	12537
517	11149
518	12132
519	13140
520	14218
521	14374
522	14530
523	15502
524	16416
525	15904
526	15372
527	16342
528	16417
529	15659
530	15860
531	17667
532	20830
533	22699
534	21375
535	20301
536	20069
537	17802
538	14890
539	15124
540	17147
541	17457
542	16602
543	17806
544	19579
545	21601
546	22541
547	21947
548	21204
549	20849
550	19863
551	20477
552	21248
553	21834
554	21832
555	20702
556	18662
557	18634
558	21695
559	25780
560	29090
561	29912
562	33276
563	35184
564	33758
565	33293
566	34368
567	34204
568	34964
569	36927
570	37564
571	36128
572	34010
573	32934
574	34102
575	37086
576	37950
577	35462
578	35738
579	41127
580	47124
581	47330
582	44833
583	45366
584	47972
585	50294
586	49967
587	49922
588	50289
589	50425
590	53738
591	58678
592	60363
593	58483
594	59682
595	64131
596	66004
597	66370
598	70115
599	73518
600	76777
601	81250
602	82368
603	82323
604	85993
605	89116
606	92038
607	96358
608	102496
609	112146
610	117615
611	116489
612	116015
613	119518
614	124728
615	127786
616	137556
617	155455
618	162899
619	167521
620	174713
621	179244
622	186360
623	197685
624	208851
625	215892
626	219154
627	227166
628	245088
629	256314
630	266422
631	276747
632	288725
633	301562
634	311504
635	319015
636	322127
637	327879
638	331029
639	328808
640	330831
641	349826
642	362819
643	363329
644	344193
645	337905
646	353989
647	367105
648	376978
649	375975
650	370268
651	367318
652	361230
653	351377
654	352913
655	359134
656	347907
657	336091
658	327517
659	320027
660	326253
661	336677
662	347262
663	341513
664	335415
665	349287
666	357607
667	358584
668	369364
669	372387
670	368224
671	369852
672	365700
673	350720
674	345167
675	337902
676	321704
677	295764
678	279009
679	275767
680	268492
681	250523
682	231681
683	217492
684	204501
685	195734
686	182783
687	167355
688	150640
689	145502
690	140097
691	130222
692	122671
693	118457
694	115209
695	119672
696	125917
697	118400
698	104954
699	92236
700	82077
701	78424
702	80679
703	85173
704	84458
705	80595
706	80156
707	75671
708	69656
709	69074
710	65679
711	63822
712	63558
713	60647
714	61216
715	65751
716	67550
717	63368
718	56418
719	54364
720	49330
721	45718
722	47479
723	50915
724	49877
725	43432
726	43954
727	44408
728	42399
729	37264
730	30774
731	30782
732	34462
733	32608
734	28240
735	28688
736	27310
737	27551
738	27766
739	25044
740	26305
741	28619
742	28059
743	25320
744	24329
745	23098
746	23242
747	25158
748	24740
749	21175
750	20023
751	21062
752	22229
753	23474
754	24823
755	26133
756	23687
757	19274
758	16453
759	18050
760	18553
761	15842
762	15801
763	19182
764	23201
765	24285
766	20326
767	16372
768	14185
769	13762
770	13392
771	13916
772	15774
773	16047
774	14560
775	15364
776	15550
777	16140
778	17506
779	17879
780	19339
781	20137
782	20583
783	18920
784	14469
785	11239
786	11802
787	13607
788	12704
789	10635
790	9157
791	10007
792	10331
793	10490
794	11701
795	11995
796	11656
797	12508
798	11106
799	10025
800	9281
801	9822
802	12342
803	14037
804	13269
805	11715
806	10897
807	12492
808	13903
809	12432
810	9320
811	7432
812	7965
813	9714
814	11162
815	11562
816	11104
817	11332
818	11823
819	11885
820	11656
821	9349
822	7643
823	7716
824	9147
825	9395
826	9861
827	9928
828	7264
829	6574
830	6979
831	7503
832	8217
833	6285
834	5527
835	8947
836	11807
837	13230
838	11928
839	9147
840	7929
841	7081
842	8318
843	6774
844	6962
845	7968
846	8502
847	8160
848	6166
849	6736
850	8433
851	9709
852	8097
853	6743
854	8565
855	12085
856	9581
857	6525
858	7315
859	7335
860	6490
861	7219
862	8046
863	8416
864	6588
865	6405
866	5935
867	4219
868	6160
869	9594
870	9382
871	7791
872	7224
873	9791
874	13694
875	14207
876	11110
877	8910
878	8488
879	7580
880	9193
881	9514
882	7253
883	5635
884	4564
885	3946
886	3413
887	5550
888	6224
889	5048
890	4858
891	4860
892	4704
893	4008
894	3083
895	3468
896	6068
897	8783
898	10977
899	11392
900	9005
901	7456
902	6296
903	5923
904	7456
905	7216
906	6456
907	6853
908	5545
909	3908
910	4491
911	4631
912	4234
913	5043
914	6271
915	7355
916	5767
917	3851
918	2661
919	3296
920	4239
921	3889
922	3978
923	4314
924	4115
925	4601
926	5662
927	4624
928	3874
929	4185
930	5246
931	4948
932	5613
933	4391
934	4485
935	5469
936	5238
937	3899
938	6311
939	5872
940	4886
941	5274
942	4965
943	3402
944	4295
945	4603
946	4297
947	4605
948	5386
949	5563
950	4315
951	4649
952	3726
953	3421
954	5072
955	6774
956	4739
957	2700
958	2259
959	2485
960	3111
961	3870
962	4283
963	4788
964	4260
965	5132
966	6347
967	4643
968	3973
969	5305
970	5473
971	4550
972	3297
973	2204
974	3276
975	4806
976	5472
977	5639
978	3885
979	2520
980	2955
981	3793
982	3656
983	2927
984	1771
985	1765
986	2893
987	5255
988	6993
989	7100
990	5893
991	5557
992	4304
993	1988
994	2187
995	3867
996	4421
997	4876
998	3187
999	2651
1000	2166
1001	1476
1002	1645
1003	2563
1004	3008
1005	3055
1006	2779
1007	2946
1008	1667
1009	2033
1010	2078
1011	2069
1012	2583
1013	4229
1014	3930
1015	1584
1016	2356
1017	4786
1018	5216
1019	4981
1020	4722
1021	6030
1022	5674
1023	4350
1024	4118