1	2298
2	2372
3	2681
4	2748
5	2745
6	2720
7	2807
8	2542
9	2388
10	2314
11	2324
12	2082
13	1999
14	2004
15	2368
16	2552
17	2864
18	2703
19	2471
20	2330
21	2199
22	2216
23	2491
24	2650
25	2976
26	3321
27	3145
28	2823
29	2325
30	2024
31	1889
32	1844
33	2142
34	2380
35	2452
36	2928
37	3007
38	3208
39	3020
40	2726
41	2192
42	2062
43	1966
44	2041
45	2214
46	2707
47	2791
48	2961
49	2819
50	2552
51	2448
52	2330
53	2317
54	2052
55	2358
56	2415
57	2986
58	3261
59	3246
60	2966
61	2580
62	2240
63	2299
64	2561
65	2405
66	2124
67	2051
68	2030
69	2474
70	3047
71	3188
72	3324
73	3418
74	3422
75	3345
76	2780
77	2308
78	2139
79	2226
80	2585
81	2826
82	3313
83	3428
84	3135
85	2714
86	2656
87	2917
88	3324
89	3370
90	3306
91	2699
92	2556
93	2126
94	2088
95	2057
96	2051
97	2107
98	2328
99	2578
100	2842
101	3104
102	3262
103	3319
104	3513
105	3317
106	3470
107	3704
108	3789
109	3356
110	3060
111	2569
112	2660
113	2301
114	2259
115	2567
116	2794
117	2732
118	2862
119	3101
120	3467
121	3963
122	3703
123	3008
124	2588
125	2350
126	2135
127	2050
128	2075
129	2130
130	2459
131	2889
132	3296
133	3630
134	3839
135	4185
136	4240
137	4359
138	4027
139	3438
140	3367
141	3672
142	3861
143	3843
144	3324
145	2936
146	2779
147	3267
148	3785
149	4049
150	3807
151	3353
152	3106
153	3204
154	3685
155	4303
156	4718
157	4486
158	4112
159	3372
160	2944
161	2723
162	3152
163	3354
164	3752
165	3787
166	3655
167	3942
168	4506
169	5140
170	5120
171	4686
172	3816
173	3738
174	3523
175	3610
176	3458
177	3304
178	3376
179	3581
180	3880
181	4094
182	4237
183	4420
184	4329
185	4043
186	4056
187	3780
188	4073
189	3991
190	3903
191	4159
192	4204
193	4412
194	4480
195	4916
196	4939
197	5066
198	4448
199	3700
200	3206
201	3400
202	3575
203	3778
204	3641
205	3504
206	3261
207	3881
208	4262
209	4609
210	4635
211	4418
212	4283
213	4173
214	4158
215	4207
216	3789
217	4016
218	4355
219	4773
220	4587
221	4205
222	3756
223	3504
224	3774
225	4293
226	4549
227	4859
228	5609
229	6071
230	6495
231	6729
232	6128
233	5107
234	4265
235	3439
236	3060
237	2779
238	2911
239	3149
240	3365
241	3891
242	4675
243	5089
244	5374
245	5347
246	5403
247	5655
248	5704
249	5623
250	5012
251	4038
252	3471
253	3348
254	3504
255	3984
256	4329
257	4300
258	4714
259	4891
260	4923
261	5023
262	4954
263	5049
264	4912
265	4787
266	4607
267	4678
268	4976
269	5572
270	5841
271	5581
272	4694
273	3876
274	3556
275	3210
276	3100
277	3364
278	3758
279	4185
280	4238
281	4166
282	4885
283	6098
284	7050
285	6579
286	5593
287	5068
288	5415
289	6037
290	5736
291	5875
292	6163
293	6606
294	6298
295	5846
296	6056
297	6214
298	6169
299	5706
300	5487
301	5620
302	5677
303	5247
304	5182
305	5214
306	5536
307	5499
308	5350
309	5833
310	6482
311	6890
312	6437
313	5918
314	5543
315	5884
316	6782
317	7534
318	7644
319	7295
320	6658
321	6420
322	6830
323	7363
324	7399
325	6669
326	6566
327	6897
328	7089
329	7016
330	7297
331	7458
332	7468
333	7554
334	7301
335	7384
336	7655
337	7371
338	6871
339	6606
340	7117
341	7503
342	7947
343	7635
344	7083
345	6922
346	6343
347	6088
348	6005
349	6491
350	6979
351	7007
352	7030
353	6797
354	6457
355	6374
356	6700
357	7256
358	7315
359	7324
360	7726
361	7841
362	7403
363	7280
364	8580
365	9940
366	10076
367	8823
368	8110
369	8050
370	8187
371	7804
372	7464
373	7493
374	7683
375	7980
376	8542
377	8658
378	9063
379	9491
380	10021
381	9996
382	9573
383	9223
384	9192
385	9175
386	8770
387	8454
388	8466
389	8042
390	7263
391	7355
392	8120
393	9110
394	9565
395	9892
396	9910
397	9083
398	8580
399	8492
400	8984
401	9081
402	9216
403	9321
404	9227
405	8964
406	9173
407	9302
408	10217
409	11049
410	12120
411	12305
412	11759
413	10726
414	10036
415	9390
416	8702
417	9344
418	9886
419	9810
420	9322
421	9772
422	10821
423	11179
424	10810
425	11423
426	12556
427	13104
428	13173
429	12914
430	13157
431	13295
432	13187
433	13147
434	12789
435	11627
436	10730
437	11193
438	11374
439	10940
440	10763
441	11339
442	11397
443	11291
444	11544
445	11744
446	11844
447	12129
448	12210
449	12610
450	12927
451	12847
452	12388
453	12048
454	11935
455	12357
456	12462
457	11611
458	11919
459	13893
460	14243
461	15068
462	15572
463	15424
464	15769
465	16061
466	15291
467	13857
468	13270
469	13575
470	12978
471	12450
472	12697
473	13968
474	15341
475	16703
476	16932
477	16323
478	16275
479	16869
480	16488
481	15206
482	14416
483	15050
484	16778
485	17447
486	17385
487	18237
488	19217
489	18962
490	18157
491	17811
492	17094
493	16690
494	17955
495	20719
496	23229
497	24238
498	23541
499	22375
500	22205
501	21397
502	20072
503	19628
504	21038
505	23226
506	24171
507	22853
508	23139
509	23234
510	22346
511	21119
512	20895
513	22036
514	23336
515	23938
516	24037
517	23796
518	24007
519	24135
520	23402
521	22520
522	23752
523	24572
524	25081
525	25011
526	24831
527	24417
528	24817
529	26287
530	27007
531	28058
532	28952
533	29066
534	26812
535	25645
536	26716
537	27632
538	26448
539	25773
540	26926
541	29356
542	31115
543	31835
544	31514
545	30438
546	28601
547	27326
548	26386
549	26228
550	28118
551	30638
552	30738
553	30371
554	29676
555	29856
556	32055
557	35395
558	35328
559	32574
560	31122
561	30684
562	31712
563	33322
564	34458
565	35603
566	37340
567	36457
568	36569
569	36563
570	35982
571	35855
572	36329
573	36046
574	36017
575	36253
576	33812
577	32590
578	34833
579	36028
580	36175
581	35248
582	35899
583	37305
584	36784
585	33795
586	31346
587	30614
588	31493
589	33174
590	34090
591	34686
592	34766
593	33841
594	33988
595	33725
596	31828
597	30033
598	30255
599	32933
600	36162
601	38281
602	37690
603	37782
604	36204
605	34404
606	34458
607	35258
608	35316
609	33787
610	32213
611	31047
612	30952
613	31144
614	29337
615	26483
616	24686
617	25029
618	25875
619	27173
620	27604
621	27540
622	29007
623	28668
624	26384
625	26484
626	27654
627	27492
628	29110
629	29748
630	27540
631	25644
632	26308
633	28409
634	28204
635	26816
636	26616
637	26694
638	26052
639	25893
640	24242
641	22647
642	23203
643	24297
644	23317
645	23946
646	24296
647	24132
648	25193
649	24940
650	25132
651	24101
652	21755
653	20504
654	20289
655	22162
656	24846
657	25653
658	23441
659	21611
660	22354
661	22618
662	21583
663	20672
664	20424
665	19943
666	20122
667	20547
668	21142
669	19348
670	17729
671	17697
672	18405
673	19541
674	19873
675	18713
676	18624
677	17661
678	16598
679	16588
680	17110
681	17208
682	16077
683	14648
684	14494
685	15060
686	14855
687	15434
688	15575
689	16583
690	16716
691	14564
692	12406
693	11969
694	12080
695	12364
696	12305
697	11840
698	11935
699	12426
700	12633
701	12847
702	12001
703	11189
704	12028
705	13120
706	13127
707	12444
708	13481
709	15214
710	15128
711	12835
712	10766
713	10235
714	11036
715	11724
716	12041
717	12527
718	13173
719	12146
720	11549
721	12038
722	11939
723	12407
724	14051
725	14352
726	13055
727	11157
728	11373
729	11654
730	11913
731	11624
732	11581
733	12702
734	13348
735	12021
736	10294
737	9333
738	9520
739	10552
740	10720
741	9828
742	8828
743	8691
744	10446
745	11110
746	10555
747	9861
748	9273
749	8713
750	8898
751	8871
752	8718
753	10505
754	10339
755	7991
756	7788
757	9332
758	9853
759	9557
760	8694
761	9374
762	10304
763	10678
764	10520
765	9676
766	8596
767	8166
768	8588
769	8658
770	8643
771	8966
772	10087
773	9883
774	8751
775	8116
776	8032
777	8341
778	8096
779	8188
780	8965
781	8859
782	8476
783	8020
784	7001
785	8077
786	9438
787	10440
788	10467
789	9925
790	8229
791	7386
792	7544
793	7044
794	6238
795	7152
796	8693
797	8602
798	7232
799	5709
800	5808
801	7304
802	7780
803	6865
804	6544
805	7066
806	7846
807	6927
808	5804
809	5495
810	5399
811	5566
812	7423
813	7970
814	6916
815	6711
816	6752
817	6942
818	7444
819	7437
820	6242
821	5188
822	5686
823	7094
824	7380
825	7479
826	7171
827	6784
828	7176
829	7073
830	6483
831	5864
832	5904
833	6003
834	5890
835	5857
836	5790
837	7402
838	8197
839	7580
840	6673
841	6221
842	6360
843	7582
844	9755
845	8845
846	7040
847	5967
848	6970
849	6791
850	6015
851	6789
852	6982
853	5454
854	5151
855	6042
856	7282
857	8806
858	7622
859	6038
860	5363
861	5070
862	6335
863	6862
864	5702
865	5393
866	5593
867	5939
868	6630
869	5759
870	3974
871	3822
872	4374
873	4085
874	4163
875	5523
876	6061
877	5295
878	4846
879	5422
880	5655
881	5038
882	4993
883	5647
884	6218
885	5881
886	5773
887	6158
888	5361
889	5105
890	6957
891	7229
892	5767
893	4884
894	3760
895	3149
896	4290
897	5444
898	5038
899	5187
900	5032
901	4771
902	4566
903	5312
904	5722
905	5419
906	5811
907	5648
908	4395
909	4487
910	5520
911	5194
912	5159
913	5420
914	5642
915	5926
916	6314
917	7312
918	6389
919	4848
920	4934
921	4573
922	4391
923	4482
924	4672
925	4613
926	4368
927	3956
928	4366
929	4922
930	2978
931	3113
932	3784
933	4672
934	4837
935	5553
936	5141
937	4896
938	4083
939	4262
940	5034
941	4925
942	3906
943	3070
944	3641
945	4040
946	4201
947	4013
948	3272
949	4007
950	5662
951	6032
952	4944
953	4763
954	5333
955	5225
956	4679
957	4358
958	4284
959	5140
960	5510
961	5536
962	4273
963	3949
964	4382
965	4013
966	4443
967	4708
968	3971
969	3901
970	4017
971	3417
972	2203
973	2683
974	2570
975	2756
976	3227
977	3430
978	3845
979	3636
980	3786
981	3748
982	3692
983	4405
984	5037
985	5149
986	4428
987	4060
988	4374
989	4953
990	4550
991	4121
992	3637
993	5220
994	5539
995	5295
996	5133
997	5112
998	4198
999	4005
1000	5342
1001	4952
1002	4536
1003	5386
1004	6728
1005	6417
1006	4822
1007	3590
1008	3897
1009	4274
1010	4144
1011	5100
1012	5911
1013	5525
1014	4307
1015	4473
1016	4356
1017	4391
1018	4237
1019	4339
1020	4893
1021	4719
1022	3793
1023	4401
1024	4288