1	4361
2	5038
3	5405
4	5180
5	4460
6	4194
7	4223
8	4322
9	4246
10	4193
11	4308
12	4301
13	4712
14	5175
15	5173
16	5187
17	4578
18	4156
19	3900
20	3414
21	3171
22	3280
23	3177
24	2994
25	2990
26	2965
27	3486
28	4470
29	5052
30	4851
31	4085
32	3558
33	3821
34	3993
35	3904
36	3172
37	2618
38	2664
39	3244
40	3598
41	3671
42	3444
43	3178
44	3235
45	3834
46	4220
47	4780
48	5075
49	5447
50	5354
51	5187
52	4768
53	4306
54	4206
55	4033
56	3924
57	4019
58	4327
59	5202
60	5748
61	5377
62	4718
63	4116
64	3868
65	3647
66	3382
67	2965
68	2960
69	2970
70	3373
71	3755
72	4150
73	4132
74	3970
75	3979
76	4260
77	4405
78	4270
79	4085
80	4065
81	4552
82	5261
83	5521
84	5448
85	4562
86	3887
87	3451
88	3911
89	4335
90	5303
91	5885
92	6290
93	6761
94	6889
95	6883
96	6556
97	6283
98	5532
99	5360
100	5538
101	5902
102	6754
103	7366
104	7089
105	6052
106	4769
107	3915
108	3844
109	4100
110	4522
111	4547
112	4291
113	3634
114	3708
115	4113
116	5136
117	5980
118	6265
119	5819
120	5100
121	4542
122	4265
123	4453
124	4834
125	5272
126	5319
127	4760
128	4438
129	4453
130	4881
131	5093
132	5257
133	5168
134	5363
135	5287
136	5630
137	5466
138	5146
139	4421
140	4242
141	4482
142	4664
143	4411
144	3405
145	2679
146	2604
147	3614
148	5034
149	6124
150	5936
151	5012
152	4157
153	3535
154	4075
155	4994
156	5869
157	5893
158	5614
159	5599
160	5776
161	6112
162	6382
163	6615
164	6843
165	6439
166	5638
167	5021
168	4852
169	4645
170	4117
171	3604
172	3359
173	3550
174	3914
175	4124
176	4194
177	4137
178	4046
179	4125
180	4144
181	4156
182	4398
183	4936
184	5580
185	6180
186	6897
187	7857
188	7713
189	6962
190	6399
191	6452
192	6678
193	6804
194	6271
195	5353
196	4679
197	4743
198	4860
199	4523
200	3770
201	3254
202	3303
203	4189
204	5438
205	5958
206	5825
207	5387
208	4902
209	5319
210	6024
211	6521
212	7172
213	7773
214	7939
215	6824
216	5419
217	4644
218	5868
219	7279
220	7533
221	6048
222	4646
223	4413
224	5303
225	5847
226	5382
227	4466
228	3874
229	3696
230	3700
231	3790
232	3816
233	3643
234	3060
235	3185
236	3882
237	4925
238	5263
239	4685
240	4111
241	4318
242	5180
243	6006
244	6080
245	6077
246	6056
247	5517
248	5083
249	4201
250	3765
251	3723
252	4130
253	4878
254	5404
255	5313
256	4958
257	4537
258	4415
259	4036
260	3908
261	3843
262	3960
263	4195
264	4064
265	3813
266	3885
267	3790
268	3828
269	4060
270	4252
271	5419
272	5979
273	5041
274	4145
275	4199
276	4480
277	5411
278	6570
279	6945
280	5841
281	4629
282	4082
283	4819
284	6201
285	7242
286	6837
287	6076
288	5224
289	4652
290	4042
291	4027
292	4736
293	5312
294	5593
295	5624
296	5288
297	4800
298	4734
299	5526
300	6286
301	6347
302	5682
303	4821
304	4726
305	5271
306	6391
307	6770
308	6350
309	5266
310	4766
311	4738
312	4377
313	4354
314	5300
315	6730
316	8142
317	8578
318	7360
319	5722
320	5230
321	5767
322	5774
323	5232
324	4895
325	5002
326	5276
327	6235
328	7273
329	7077
330	6369
331	5402
332	5151
333	5298
334	6371
335	8141
336	9121
337	8427
338	6632
339	5255
340	4561
341	4760
342	5224
343	6147
344	6412
345	6126
346	5460
347	5324
348	5225
349	4860
350	4467
351	4109
352	4520
353	5625
354	5825
355	4820
356	3760
357	3471
358	3977
359	4467
360	4485
361	4510
362	4884
363	5832
364	7386
365	8753
366	8441
367	6893
368	5641
369	5134
370	5131
371	5188
372	5812
373	6708
374	6681
375	6270
376	6064
377	6865
378	8655
379	9791
380	9669
381	9549
382	9588
383	9395
384	9632
385	10079
386	10928
387	11344
388	10696
389	10261
390	10003
391	8862
392	8205
393	7476
394	5612
395	4937
396	6084
397	8372
398	9575
399	7901
400	5933
401	5031
402	4920
403	5311
404	6333
405	7283
406	8141
407	8276
408	7778
409	7316
410	7162
411	6875
412	7278
413	7590
414	7254
415	6319
416	6261
417	6547
418	7397
419	8969
420	9948
421	10334
422	10013
423	9807
424	9434
425	8745
426	8684
427	8410
428	7723
429	7103
430	7029
431	6792
432	6565
433	7151
434	8029
435	9093
436	8729
437	8188
438	8089
439	8006
440	7482
441	6184
442	5692
443	6479
444	8676
445	10335
446	10182
447	8066
448	5731
449	5832
450	8006
451	8931
452	8648
453	8275
454	8222
455	8087
456	7853
457	7937
458	8829
459	9536
460	9639
461	8909
462	7867
463	7908
464	8375
465	7902
466	6878
467	6817
468	8324
469	10552
470	11104
471	10126
472	8761
473	8369
474	9261
475	10426
476	10530
477	9852
478	8980
479	8417
480	8620
481	8657
482	8578
483	8889
484	9918
485	10473
486	10222
487	9860
488	9425
489	9905
490	11732
491	13372
492	12768
493	13370
494	14982
495	16169
496	15511
497	13111
498	11894
499	11659
500	12399
501	12580
502	12866
503	13957
504	14269
505	12953
506	12935
507	14947
508	15983
509	14698
510	12761
511	13291
512	14742
513	15660
514	15160
515	13740
516	12789
517	13837
518	16123
519	16528
520	15767
521	15766
522	17016
523	17669
524	16927
525	17200
526	17762
527	16909
528	17304
529	17825
530	18449
531	18221
532	16480
533	16092
534	15218
535	14494
536	15521
537	17783
538	17834
539	18008
540	20393
541	22987
542	21505
543	18344
544	18050
545	21151
546	23072
547	21144
548	17171
549	14118
550	14194
551	17942
552	22324
553	24661
554	24433
555	24167
556	24087
557	24133
558	22965
559	24062
560	28067
561	30435
562	31194
563	28578
564	27365
565	29279
566	32473
567	32440
568	32816
569	37233
570	44236
571	45172
572	41116
573	36972
574	35374
575	37164
576	38808
577	37255
578	38227
579	40744
580	43632
581	45581
582	45265
583	42483
584	41410
585	42661
586	44844
587	46966
588	50875
589	56926
590	59973
591	57666
592	52343
593	50953
594	53729
595	56625
596	57661
597	59774
598	65757
599	68320
600	67901
601	67641
602	64509
603	65509
604	74754
605	85166
606	88699
607	83228
608	79091
609	86863
610	96467
611	99956
612	107359
613	111718
614	112170
615	109181
616	106365
617	107098
618	109641
619	119288
620	128292
621	139022
622	149336
623	151711
624	147618
625	149575
626	154442
627	152653
628	159213
629	165706
630	168607
631	171468
632	178007
633	191227
634	198384
635	201319
636	206082
637	206484
638	204353
639	205921
640	206704
641	207920
642	202674
643	199728
644	199144
645	201567
646	198083
647	203402
648	221533
649	226561
650	224219
651	222316
652	217065
653	212754
654	216100
655	229114
656	228629
657	220500
658	218693
659	226216
660	232105
661	228493
662	219775
663	217885
664	222622
665	220070
666	213896
667	211920
668	207443
669	207197
670	206392
671	207269
672	208147
673	208660
674	207551
675	201829
676	198551
677	188124
678	176842
679	167004
680	165058
681	161011
682	154711
683	148589
684	143270
685	139684
686	132823
687	124851
688	110118
689	103296
690	99040
691	93012
692	92036
693	90175
694	85779
695	79765
696	78365
697	81506
698	80552
699	74623
700	71364
701	70459
702	70612
703	72139
704	74307
705	72267
706	65126
707	58194
708	55074
709	54758
710	56849
711	57287
712	54774
713	52240
714	48161
715	43099
716	42889
717	44667
718	41866
719	38355
720	37879
721	35077
722	36026
723	34177
724	33857
725	33605
726	33113
727	33722
728	35793
729	37232
730	35181
731	30720
732	28926
733	31109
734	30700
735	28140
736	26410
737	27020
738	26401
739	25545
740	25068
741	25049
742	22003
743	19733
744	21751
745	23393
746	24513
747	24211
748	24401
749	23899
750	25097
751	25389
752	23346
753	22094
754	22128
755	23647
756	22263
757	21699
758	22494
759	22206
760	20465
761	19245
762	17833
763	17919
764	18313
765	18570
766	18090
767	16279
768	14785
769	16393
770	19445
771	21084
772	19405
773	15024
774	13032
775	15513
776	18898
777	19181
778	17603
779	15928
780	14007
781	13948
782	14923
783	15120
784	15007
785	14055
786	14222
787	16892
788	17998
789	15135
790	14346
791	13468
792	12614
793	13521
794	14942
795	13777
796	11623
797	9201
798	9547
799	11172
800	12394
801	12406
802	11971
803	12369
804	12836
805	12204
806	10471
807	9589
808	10847
809	11133
810	10683
811	10624
812	11383
813	12695
814	9491
815	8939
816	10504
817	11001
818	10674
819	12492
820	14838
821	13270
822	8712
823	8478
824	8749
825	8421
826	9628
827	11167
828	11048
829	11760
830	10439
831	9731
832	10394
833	11287
834	11374
835	10222
836	10042
837	12068
838	10530
839	9904
840	9827
841	11094
842	11950
843	7666
844	5506
845	5563
846	6722
847	8133
848	8306
849	7972
850	8895
851	10154
852	7838
853	7615
854	9707
855	10227
856	8689
857	9769
858	9511
859	8025
860	7871
861	6393
862	6458
863	6215
864	5074
865	5505
866	6378
867	6038
868	4993
869	4135
870	5777
871	9062
872	8830
873	9012
874	10404
875	11347
876	10224
877	7675
878	4582
879	5694
880	5844
881	5794
882	6847
883	6285
884	6577
885	6199
886	6012
887	6151
888	5257
889	4294
890	4285
891	3069
892	2393
893	2777
894	5647
895	9854
896	11271
897	7672
898	5238
899	5358
900	6100
901	6386
902	7931
903	7752
904	5730
905	6194
906	6722
907	5613
908	4920
909	3953
910	5677
911	5832
912	4962
913	5880
914	6400
915	6828
916	5488
917	4652
918	3877
919	2843
920	3013
921	4090
922	6152
923	7383
924	6534
925	5093
926	4893
927	5371
928	4273
929	3256
930	3767
931	5362
932	6421
933	6985
934	6711
935	6203
936	5383
937	5573
938	5850
939	7279
940	8382
941	10288
942	8032
943	7063
944	5669
945	3805
946	3159
947	4561
948	5647
949	5632
950	5111
951	6367
952	7184
953	7462
954	6495
955	4590
956	4864
957	6054
958	7180
959	6386
960	5513
961	7108
962	8747
963	8424
964	9903
965	7155
966	4550
967	3853
968	5746
969	5273
970	4337
971	5305
972	5748
973	6310
974	7621
975	5366
976	4635
977	3889
978	3703
979	3770
980	5447
981	6813
982	8026
983	6446
984	7162
985	8397
986	6989
987	6275
988	3488
989	2618
990	3267
991	3566
992	3320
993	4599
994	5690
995	4270
996	4483
997	5467
998	5088
999	4869
1000	4621
1001	4590
1002	3252
1003	3072
1004	4519
1005	5954
1006	6336
1007	5813
1008	6095
1009	4459
1010	2005
1011	2657
1012	3753
1013	3915
1014	3694
1015	2952
1016	1587
1017	998
1018	1240
1019	2502
1020	5615
1021	6788
1022	6196
1023	5743
1024	4210