1	1329
2	1326
3	1446
4	1723
5	1922
6	2042
7	2199
8	1928
9	1640
10	1349
11	1113
12	1171
13	1364
14	1566
15	1823
16	1780
17	1750
18	1746
19	1834
20	1988
21	1851
22	1798
23	1801
24	1753
25	1760
26	2218
27	2189
28	2115
29	1683
30	1441
31	1415
32	1373
33	1627
34	1839
35	1798
36	1661
37	1622
38	1792
39	1951
40	2168
41	2237
42	2091
43	1748
44	1701
45	1535
46	1640
47	1283
48	1445
49	1356
50	1459
51	1215
52	1162
53	1236
54	1159
55	1250
56	1101
57	1397
58	1598
59	1742
60	2073
61	2127
62	1860
63	1592
64	1455
65	1393
66	1467
67	1744
68	1884
69	1988
70	2204
71	1957
72	1830
73	1565
74	1489
75	1391
76	1320
77	1341
78	1064
79	1386
80	1445
81	1737
82	2055
83	2202
84	2110
85	1952
86	1785
87	1645
88	1793
89	2043
90	2258
91	1944
92	1860
93	1708
94	2121
95	2288
96	2392
97	2216
98	2055
99	2012
100	1965
101	1959
102	2195
103	2271
104	2466
105	2334
106	2398
107	2444
108	2520
109	2453
110	2508
111	2291
112	2238
113	2074
114	1999
115	2295
116	2314
117	2067
118	2024
119	1929
120	1783
121	1983
122	1969
123	1828
124	1747
125	2005
126	2034
127	2217
128	2455
129	2345
130	2493
131	2490
132	2306
133	2145
134	1795
135	1823
136	1818
137	1933
138	1975
139	1991
140	1767
141	1567
142	1311
143	1429
144	1587
145	1888
146	2183
147	2678
148	2682
149	2507
150	2332
151	2125
152	2343
153	2439
154	2424
155	2244
156	1946
157	1733
158	1824
159	1642
160	1664
161	1717
162	2225
163	2399
164	2583
165	2277
166	2178
167	2231
168	2025
169	2040
170	2019
171	2087
172	1888
173	1963
174	1868
175	1928
176	2219
177	2461
178	2122
179	1926
180	1572
181	1645
182	1594
183	1778
184	1581
185	1603
186	1783
187	1933
188	2036
189	2173
190	2295
191	2501
192	2853
193	3176
194	3501
195	3232
196	2855
197	2570
198	2767
199	3067
200	3297
201	3303
202	3214
203	3404
204	3201
205	2937
206	2726
207	2855
208	3096
209	3379
210	3183
211	2855
212	2327
213	2420
214	2563
215	3043
216	3123
217	3026
218	2466
219	2243
220	2023
221	2209
222	2502
223	2560
224	2235
225	1904
226	1519
227	1852
228	2130
229	2411
230	2531
231	2916
232	2922
233	2973
234	3133
235	3231
236	3283
237	3269
238	3218
239	3097
240	3308
241	3466
242	3763
243	3536
244	3522
245	3247
246	3315
247	3282
248	3220
249	2980
250	2657
251	2459
252	2447
253	2810
254	3116
255	3059
256	2742
257	2828
258	3515
259	4177
260	4028
261	3718
262	3198
263	3050
264	2989
265	3160
266	3325
267	3358
268	3442
269	3138
270	2581
271	2313
272	2608
273	3102
274	3649
275	3892
276	3991
277	3911
278	3763
279	3884
280	3880
281	3924
282	4125
283	4131
284	3801
285	3835
286	3915
287	3965
288	4023
289	3983
290	3921
291	4261
292	4297
293	4235
294	4336
295	4337
296	4890
297	5200
298	5142
299	4325
300	3751
301	3567
302	3610
303	3680
304	3778
305	4049
306	4423
307	4213
308	3810
309	3669
310	3206
311	2790
312	2749
313	3009
314	3647
315	4038
316	4047
317	3960
318	4413
319	4983
320	5004
321	4848
322	4801
323	4840
324	4972
325	4597
326	4690
327	4478
328	4227
329	4049
330	4295
331	4613
332	4513
333	4276
334	4342
335	4839
336	5568
337	6012
338	5922
339	5453
340	5146
341	4957
342	4960
343	5101
344	5228
345	5692
346	5984
347	6267
348	5997
349	5694
350	5144
351	4818
352	5023
353	5406
354	5653
355	5584
356	4960
357	4793
358	4546
359	4621
360	4916
361	5108
362	4643
363	4616
364	4564
365	4693
366	4614
367	4579
368	4562
369	4923
370	5120
371	4590
372	4243
373	4483
374	5093
375	5272
376	5442
377	5261
378	5274
379	5487
380	6714
381	7806
382	7828
383	6604
384	6035
385	6094
386	5741
387	5201
388	5162
389	5665
390	6368
391	6495
392	6170
393	5860
394	6063
395	6453
396	7316
397	7483
398	6998
399	6979
400	7725
401	7658
402	6783
403	6091
404	6061
405	6192
406	6440
407	6814
408	7660
409	8065
410	7875
411	7318
412	6869
413	6502
414	6997
415	7699
416	8060
417	8544
418	8756
419	8157
420	7348
421	6486
422	6505
423	7200
424	7930
425	7933
426	7259
427	6588
428	6545
429	7369
430	8113
431	8247
432	8042
433	7716
434	7420
435	6834
436	6317
437	6454
438	6798
439	7142
440	7743
441	8636
442	8818
443	8776
444	8460
445	8717
446	9392
447	10037
448	10695
449	10607
450	9689
451	8201
452	7228
453	7256
454	7966
455	8727
456	9539
457	10744
458	10960
459	10248
460	9553
461	9623
462	9681
463	9410
464	9127
465	9486
466	9362
467	9203
468	10282
469	12130
470	11991
471	10681
472	9232
473	8502
474	8254
475	8064
476	7969
477	8005
478	7972
479	8967
480	9967
481	11144
482	11570
483	11217
484	9961
485	9233
486	8768
487	8425
488	9084
489	10715
490	11558
491	11528
492	11435
493	11668
494	11913
495	13070
496	13704
497	13421
498	12951
499	12476
500	12583
501	13172
502	14186
503	14414
504	14424
505	14908
506	14691
507	14790
508	16001
509	15782
510	14674
511	13710
512	13700
513	13225
514	12358
515	11693
516	12348
517	15111
518	17303
519	16735
520	15675
521	14358
522	13770
523	14338
524	15302
525	15891
526	16461
527	16557
528	17199
529	18087
530	18181
531	17201
532	15871
533	16153
534	17002
535	17305
536	17001
537	16880
538	16777
539	16419
540	16791
541	16927
542	17105
543	18317
544	19174
545	19457
546	18891
547	19254
548	18706
549	19365
550	20183
551	19389
552	18410
553	17988
554	15965
555	14957
556	15993
557	18552
558	19680
559	20583
560	21896
561	21509
562	20259
563	19869
564	20661
565	21604
566	22231
567	22314
568	22419
569	21288
570	20459
571	20654
572	21140
573	21601
574	21124
575	21284
576	22060
577	22217
578	22915
579	24224
580	25129
581	25226
582	25247
583	24561
584	23614
585	22232
586	21190
587	20272
588	19628
589	19290
590	19149
591	20216
592	20776
593	21452
594	22431
595	20597
596	19135
597	20190
598	23470
599	25330
600	25935
601	26492
602	25374
603	23257
604	21363
605	20255
606	20423
607	21642
608	23235
609	22076
610	18803
611	17765
612	19973
613	21679
614	19970
615	18198
616	17847
617	18462
618	18205
619	18135
620	18003
621	17833
622	17299
623	17480
624	18408
625	19538
626	19710
627	19350
628	18641
629	17241
630	17118
631	17706
632	17591
633	16724
634	15363
635	14845
636	15669
637	16338
638	16440
639	16498
640	16583
641	16517
642	15988
643	15735
644	14270
645	13378
646	13923
647	14448
648	14152
649	13722
650	15165
651	15743
652	14981
653	14983
654	16469
655	16906
656	15579
657	14932
658	14704
659	13865
660	12280
661	9976
662	9992
663	12066
664	13434
665	13857
666	13508
667	11562
668	11160
669	11152
670	10845
671	11173
672	10979
673	10490
674	11976
675	13045
676	11956
677	10746
678	10843
679	11079
680	11073
681	10403
682	10263
683	11501
684	12143
685	11092
686	10462
687	11608
688	12099
689	10859
690	10907
691	11184
692	10539
693	9196
694	7603
695	7895
696	8579
697	8321
698	8787
699	9472
700	9186
701	9903
702	10255
703	9859
704	9735
705	8827
706	7182
707	7024
708	8645
709	9796
710	9739
711	9695
712	9851
713	8675
714	8269
715	8975
716	8861
717	7732
718	6359
719	5876
720	6922
721	8912
722	9675
723	9393
724	8957
725	8232
726	7487
727	7376
728	8374
729	9307
730	8548
731	7030
732	6947
733	7908
734	8566
735	8405
736	7418
737	7354
738	7894
739	7337
740	7100
741	7468
742	8510
743	8046
744	8106
745	7280
746	6307
747	5590
748	5458
749	5610
750	5574
751	5357
752	6815
753	7519
754	5808
755	5393
756	5473
757	5692
758	5884
759	5814
760	6392
761	6444
762	5923
763	6699
764	6587
765	5483
766	5432
767	5575
768	6098
769	7491
770	7017
771	5689
772	5753
773	5212
774	5209
775	5914
776	6878
777	7059
778	6439
779	6961
780	7398
781	5851
782	4802
783	4537
784	4262
785	5242
786	5218
787	4325
788	4276
789	4769
790	4864
791	4600
792	3911
793	4162
794	4879
795	5399
796	5114
797	4578
798	5409
799	5451
800	4827
801	4154
802	3708
803	4034
804	4430
805	4927
806	4266
807	3368
808	3225
809	3042
810	3697
811	4679
812	4659
813	4053
814	4459
815	4371
816	4157
817	4112
818	4313
819	4394
820	4045
821	4242
822	4875
823	5391
824	4978
825	4299
826	4407
827	4342
828	3949
829	3420
830	3140
831	4026
832	4698
833	4054
834	3659
835	3464
836	3778
837	4084
838	4127
839	3848
840	4356
841	4362
842	4197
843	3822
844	3730
845	3923
846	4191
847	3677
848	3384
849	3640
850	4351
851	4818
852	4802
853	4514
854	4347
855	4145
856	3825
857	4130
858	4070
859	3459
860	3245
861	4080
862	4910
863	4732
864	4069
865	3351
866	2854
867	2972
868	3444
869	4004
870	4373
871	4745
872	5079
873	4602
874	4736
875	4596
876	2903
877	2552
878	2696
879	2561
880	2929
881	4776
882	4724
883	3829
884	3484
885	2924
886	2131
887	2023
888	2352
889	3150
890	3649
891	3889
892	3093
893	3178
894	4657
895	6114
896	4953
897	3806
898	3490
899	2857
900	2353
901	2649
902	2705
903	3445
904	3985
905	3884
906	3273
907	2547
908	2074
909	2564
910	4025
911	4877
912	4667
913	4743
914	3661
915	3050
916	3361
917	3486
918	2929
919	3358
920	3678
921	3855
922	3104
923	2669
924	2443
925	2871
926	2565
927	1955
928	2252
929	2533
930	2713
931	3670
932	4257
933	3649
934	3695
935	3975
936	3583
937	2332
938	2589
939	3584
940	4468
941	3142
942	2687
943	3290
944	3144
945	3935
946	4896
947	4636
948	3030
949	2301
950	2092
951	2246
952	2270
953	2307
954	2391
955	2920
956	2438
957	2083
958	2759
959	2812
960	3019
961	3879
962	3322
963	3113
964	3960
965	3622
966	2361
967	2306
968	2326
969	1743
970	1796
971	2248
972	2478
973	3341
974	2823
975	2058
976	2343
977	2596
978	3119
979	3441
980	3630
981	3265
982	2802
983	1942
984	2039
985	2793
986	2606
987	2186
988	2903
989	3456
990	3268
991	2901
992	2703
993	3327
994	3710
995	3359
996	3061
997	2897
998	3254
999	3224
1000	3414
1001	2897
1002	2777
1003	3010
1004	2763
1005	2181
1006	2304
1007	3249
1008	3617
1009	3779
1010	3600
1011	3418
1012	2385
1013	2424
1014	3646
1015	2581
1016	1272
1017	1715
1018	1943
1019	2094
1020	2214
1021	3187
1022	2987
1023	2867
1024	3048