1	1396
2	1224
3	1262
4	1184
5	1091
6	1130
7	1254
8	1213
9	1336
10	1569
11	1822
12	2120
13	2387
14	2298
15	2258
16	2056
17	1796
18	1641
19	1600
20	1625
21	1511
22	1472
23	1521
24	1506
25	1552
26	1695
27	1680
28	1607
29	1576
30	1552
31	1501
32	1302
33	1423
34	1536
35	1803
36	1947
37	1670
38	1693
39	1400
40	1341
41	1460
42	1742
43	2186
44	2506
45	2658
46	2627
47	2313
48	2391
49	2327
50	2482
51	2439
52	2473
53	2702
54	2509
55	2284
56	2033
57	2172
58	2047
59	1911
60	1935
61	1849
62	1947
63	2243
64	2306
65	2382
66	2105
67	2025
68	1756
69	1458
70	1433
71	1438
72	1518
73	1760
74	2004
75	1782
76	1417
77	1340
78	1196
79	1355
80	1376
81	1551
82	1634
83	1811
84	1624
85	1530
86	1631
87	1644
88	1615
89	1389
90	1507
91	1435
92	1860
93	2228
94	2610
95	2878
96	2730
97	2145
98	1624
99	1200
100	1228
101	1268
102	1382
103	1073
104	1062
105	917
106	933
107	1018
108	1071
109	1140
110	1447
111	1534
112	1814
113	1961
114	1780
115	1985
116	1893
117	1925
118	1826
119	1832
120	1747
121	2127
122	2411
123	2461
124	2585
125	2655
126	2604
127	2641
128	2878
129	2837
130	2742
131	2496
132	2352
133	2102
134	1983
135	2134
136	2162
137	1889
138	1695
139	1710
140	1824
141	2316
142	2546
143	2854
144	2495
145	2183
146	1882
147	2087
148	2379
149	2507
150	2428
151	2472
152	2641
153	2400
154	2414
155	2603
156	2925
157	2811
158	2527
159	2012
160	1681
161	1303
162	1440
163	1413
164	1768
165	1856
166	1946
167	1998
168	1712
169	1668
170	1660
171	1841
172	1982
173	1979
174	1889
175	1934
176	1997
177	2030
178	1853
179	2187
180	2699
181	2888
182	2834
183	2739
184	2353
185	2133
186	2067
187	2176
188	2397
189	2544
190	2656
191	2622
192	2683
193	2903
194	2930
195	2651
196	2545
197	2755
198	3003
199	3084
200	2720
201	2384
202	1992
203	2209
204	2578
205	2683
206	2610
207	2603
208	2732
209	2963
210	2894
211	2638
212	2325
213	2249
214	2279
215	2453
216	2039
217	1643
218	1390
219	1393
220	1830
221	2141
222	2565
223	2619
224	2605
225	2500
226	2344
227	2681
228	2670
229	2539
230	2489
231	2808
232	3070
233	3112
234	3111
235	2825
236	2851
237	2839
238	2856
239	3242
240	3592
241	3841
242	3972
243	3559
244	3423
245	3257
246	3521
247	3363
248	3122
249	2764
250	2689
251	3187
252	3503
253	3352
254	3206
255	3123
256	3345
257	3250
258	3468
259	3536
260	3451
261	3538
262	3657
263	3758
264	3696
265	3366
266	2718
267	2297
268	2435
269	2475
270	2594
271	3085
272	3759
273	4180
274	4208
275	3655
276	3138
277	2771
278	2663
279	2612
280	2589
281	3011
282	3598
283	4041
284	4209
285	4067
286	4029
287	3892
288	3592
289	3266
290	3303
291	3495
292	3193
293	3167
294	3168
295	3253
296	3584
297	3477
298	3380
299	3631
300	4013
301	3993
302	3639
303	3233
304	2926
305	2636
306	2967
307	3198
308	3505
309	3437
310	2975
311	2888
312	2857
313	3361
314	4013
315	4392
316	4906
317	5094
318	5074
319	4600
320	4297
321	3755
322	3662
323	3858
324	3957
325	3676
326	3854
327	4238
328	4683
329	4686
330	4582
331	4182
332	3753
333	3656
334	3923
335	4515
336	5177
337	4655
338	4198
339	4020
340	4092
341	3994
342	3584
343	3397
344	3390
345	3571
346	3800
347	4252
348	4397
349	4379
350	4361
351	4223
352	4124
353	4172
354	4182
355	3906
356	4386
357	4879
358	4546
359	4071
360	3845
361	4012
362	3946
363	4159
364	4761
365	5557
366	5835
367	5405
368	4572
369	4666
370	5227
371	5763
372	6141
373	5872
374	5835
375	6101
376	6253
377	5488
378	4841
379	4827
380	5315
381	5533
382	5601
383	5531
384	5896
385	6064
386	6261
387	6226
388	6395
389	6141
390	5854
391	6078
392	6321
393	6064
394	4962
395	4797
396	5594
397	6183
398	6700
399	6810
400	6825
401	6521
402	6047
403	6204
404	6466
405	6346
406	6174
407	5956
408	5683
409	5633
410	5812
411	6188
412	6484
413	6494
414	6315
415	5990
416	5864
417	6008
418	6055
419	5997
420	5873
421	5569
422	6119
423	7413
424	8095
425	8081
426	8122
427	8373
428	8233
429	7828
430	7371
431	7091
432	7148
433	7585
434	8437
435	8512
436	7416
437	6587
438	6329
439	6497
440	6801
441	7368
442	7150
443	6480
444	6471
445	6473
446	6547
447	6960
448	7367
449	7474
450	7571
451	7577
452	7645
453	7932
454	8517
455	8518
456	9105
457	9987
458	10495
459	9851
460	8683
461	8357
462	8232
463	8861
464	8896
465	8828
466	9157
467	9200
468	8958
469	8877
470	8218
471	8311
472	10067
473	11873
474	12465
475	12215
476	11750
477	11265
478	10728
479	10355
480	10127
481	10246
482	10048
483	9919
484	10040
485	10004
486	10176
487	10774
488	10691
489	10565
490	11006
491	11466
492	11434
493	11952
494	12995
495	13852
496	13279
497	12362
498	12543
499	13366
500	14173
501	13394
502	12145
503	12599
504	13057
505	13186
506	12955
507	12579
508	11773
509	11435
510	12446
511	13023
512	12972
513	13139
514	14231
515	16831
516	19049
517	19081
518	17557
519	15826
520	15328
521	15016
522	14289
523	13860
524	14355
525	14940
526	15191
527	15308
528	16116
529	16430
530	15658
531	15001
532	15215
533	15906
534	16224
535	17158
536	18018
537	17491
538	17476
539	18849
540	20626
541	21727
542	20287
543	18681
544	18270
545	19902
546	20720
547	20427
548	18924
549	17884
550	17383
551	16757
552	17397
553	18413
554	18574
555	18203
556	19193
557	22550
558	24164
559	22994
560	22016
561	20882
562	18956
563	17917
564	18227
565	18618
566	20265
567	21594
568	21083
569	19046
570	19107
571	19815
572	20086
573	20876
574	20555
575	20567
576	21379
577	21718
578	22960
579	23852
580	22608
581	20922
582	20582
583	19807
584	20246
585	22249
586	22804
587	21661
588	20762
589	21143
590	21323
591	20859
592	21226
593	22800
594	22639
595	20887
596	20830
597	21986
598	23244
599	22397
600	21206
601	21150
602	21063
603	20693
604	19244
605	18360
606	19136
607	19581
608	19158
609	20003
610	22331
611	22957
612	21816
613	21093
614	19202
615	18592
616	19811
617	19698
618	18008
619	17316
620	17597
621	18489
622	18309
623	17493
624	17767
625	18147
626	17150
627	15768
628	15241
629	15808
630	17722
631	18336
632	17073
633	16661
634	16944
635	16940
636	16819
637	15982
638	14968
639	13880
640	14102
641	15033
642	15133
643	14137
644	12816
645	13286
646	14048
647	14240
648	13741
649	12884
650	13577
651	13757
652	12906
653	12480
654	14135
655	15982
656	14779
657	12459
658	12160
659	12535
660	12925
661	14288
662	15180
663	15280
664	16357
665	15239
666	12514
667	10970
668	11949
669	12705
670	11462
671	10898
672	12099
673	13099
674	13535
675	14268
676	14139
677	12104
678	10785
679	9887
680	10163
681	10227
682	10370
683	9357
684	8565
685	9765
686	12363
687	13644
688	12021
689	10614
690	10501
691	10661
692	10395
693	10753
694	9881
695	8747
696	7504
697	6574
698	6754
699	7977
700	9866
701	11589
702	11286
703	9206
704	8179
705	7951
706	7824
707	8975
708	8976
709	7751
710	6793
711	6886
712	7669
713	7411
714	7229
715	7420
716	8324
717	9772
718	9859
719	7882
720	6688
721	6139
722	6128
723	6155
724	6368
725	7511
726	9377
727	9617
728	9184
729	8334
730	7189
731	7242
732	7765
733	8303
734	9118
735	8325
736	7363
737	6143
738	5584
739	6086
740	6568
741	7343
742	7347
743	6833
744	7448
745	6618
746	4904
747	5092
748	5984
749	6397
750	7577
751	8961
752	8303
753	7405
754	6585
755	5678
756	4999
757	5254
758	6608
759	8048
760	7494
761	6487
762	5981
763	4536
764	3806
765	5531
766	6234
767	5843
768	6472
769	6674
770	7379
771	8573
772	7389
773	6743
774	7249
775	5906
776	5381
777	5026
778	4450
779	4355
780	4857
781	4526
782	3402
783	3729
784	4638
785	5110
786	4464
787	4302
788	4482
789	4909
790	5559
791	6365
792	5983
793	5712
794	5027
795	3942
796	4327
797	5231
798	5390
799	4858
800	4774
801	5743
802	5126
803	4630
804	4560
805	4281
806	4436
807	4135
808	4094
809	4541
810	4859
811	4370
812	4640
813	4777
814	4881
815	4931
816	5139
817	5559
818	5282
819	4808
820	4172
821	4218
822	4526
823	5695
824	6170
825	4820
826	4091
827	4806
828	5766
829	5432
830	4457
831	4540
832	4297
833	4535
834	5121
835	5677
836	5621
837	5536
838	4457
839	3482
840	3104
841	3167
842	3014
843	2536
844	3106
845	3693
846	3884
847	3327
848	3962
849	3665
850	2963
851	2911
852	3276
853	3247
854	3427
855	3532
856	3150
857	3185
858	2953
859	3146
860	2891
861	3131
862	2810
863	2398
864	2944
865	4133
866	4446
867	4373
868	4798
869	5112
870	4810
871	3980
872	3396
873	3988
874	3227
875	3330
876	4382
877	4169
878	4152
879	4103
880	3661
881	3269
882	3616
883	3933
884	3787
885	3362
886	2809
887	3285
888	4420
889	4540
890	5342
891	5324
892	3466
893	2375
894	2665
895	3946
896	4702
897	3906
898	4695
899	4847
900	4161
901	3921
902	3224
903	2681
904	3400
905	4534
906	3382
907	3272
908	3963
909	4042
910	3963
911	3423
912	3012
913	3395
914	2951
915	2801
916	3579
917	3952
918	2913
919	2648
920	3864
921	5088
922	4367
923	3900
924	3622
925	3305
926	2826
927	2625
928	3499
929	4465
930	3902
931	2690
932	2242
933	2044
934	2318
935	2570
936	2748
937	3510
938	4346
939	4340
940	4752
941	4441
942	4248
943	3278
944	2492
945	2690
946	2949
947	3285
948	3190
949	2816
950	2498
951	2967
952	3451
953	3409
954	2489
955	2215
956	2579
957	2411
958	3197
959	3415
960	2785
961	3046
962	3026
963	3216
964	3340
965	3476
966	2331
967	2523
968	4485
969	4696
970	3688
971	2967
972	2676
973	2189
974	1642
975	1847
976	3339
977	3519
978	4636
979	4542
980	3592
981	2787
982	2091
983	1873
984	2107
985	2581
986	3061
987	3200
988	3293
989	4077
990	3549
991	2845
992	2481
993	3007
994	3519
995	3469
996	3199
997	2471
998	2124
999	2117
1000	2215
1001	2883
1002	3191
1003	3372
1004	3990
1005	4122
1006	3227
1007	2398
1008	2425
1009	2272
1010	2934
1011	3570
1012	3290
1013	2197
1014	1958
1015	2267
1016	1854
1017	2185
1018	2620
1019	2768
1020	2791
1021	2308
1022	3191
1023	4411
1024	3689