1	2370
2	2172
3	2248
4	2172
5	2170
6	2129
7	2231
8	2241
9	2359
10	2331
11	2324
12	1983
13	1968
14	2194
15	2246
16	2492
17	2392
18	2224
19	2330
20	2414
21	2459
22	2477
23	2546
24	2369
25	2276
26	2166
27	2152
28	2069
29	1970
30	2033
31	1906
32	2106
33	2276
34	2205
35	2309
36	2309
37	2673
38	2773
39	3098
40	3304
41	3310
42	3003
43	2544
44	2376
45	2399
46	2162
47	2144
48	2203
49	2383
50	2298
51	2139
52	2038
53	1889
54	1999
55	2126
56	2292
57	2607
58	2886
59	3174
60	3242
61	3117
62	2736
63	2522
64	2309
65	2032
66	2072
67	1824
68	1995
69	1873
70	2032
71	2002
72	1912
73	2012
74	2220
75	2469
76	2696
77	2760
78	2442
79	2272
80	2311
81	2356
82	2410
83	2406
84	2460
85	2592
86	2726
87	2856
88	2870
89	2732
90	2818
91	2845
92	2832
93	2782
94	2653
95	2795
96	2905
97	2857
98	3050
99	2977
100	2859
101	2879
102	3041
103	3330
104	3541
105	3619
106	3889
107	4254
108	4359
109	4619
110	5004
111	5678
112	6456
113	7141
114	7380
115	7662
116	7909
117	8020
118	7953
119	8230
120	8498
121	9124
122	9312
123	9012
124	8294
125	7489
126	6510
127	5322
128	4384
129	3833
130	3935
131	4023
132	3963
133	3554
134	3262
135	3225
136	3465
137	3485
138	3303
139	3048
140	3000
141	3185
142	3498
143	3502
144	3348
145	3115
146	3061
147	2884
148	2762
149	2861
150	2787
151	2575
152	2544
153	2185
154	2258
155	2372
156	2343
157	2286
158	2036
159	2038
160	2145
161	2110
162	2216
163	2379
164	2559
165	2218
166	2074
167	1832
168	1860
169	1940
170	2210
171	2585
172	2452
173	2345
174	2284
175	2353
176	2513
177	2786
178	2897
179	2729
180	2672
181	2345
182	2427
183	2214
184	2246
185	2134
186	2075
187	2021
188	1837
189	1782
190	1707
191	1840
192	1978
193	2142
194	2185
195	2436
196	2562
197	2546
198	2241
199	2078
200	1955
201	1928
202	1826
203	1875
204	1920
205	2168
206	2253
207	2132
208	2127
209	1974
210	2069
211	2093
212	2310
213	2350
214	2346
215	2253
216	2047
217	2149
218	2268
219	2461
220	2389
221	2387
222	2140
223	1966
224	1791
225	1614
226	1779
227	2025
228	2307
229	2315
230	2308
231	2454
232	2643
233	2806
234	2893
235	2939
236	3020
237	2553
238	2300
239	2156
240	2481
241	2662
242	2673
243	2474
244	2333
245	2438
246	2604
247	2464
248	2205
249	1948
250	2027
251	2043
252	1924
253	1835
254	1792
255	1815
256	1709
257	1735
258	1860
259	2194
260	2471
261	2629
262	2469
263	2411
264	2297
265	1933
266	1803
267	1703
268	1974
269	2164
270	2330
271	2467
272	2298
273	2190
274	2249
275	2358
276	2566
277	2596
278	2434
279	2240
280	2173
281	1813
282	1845
283	1687
284	1648
285	1515
286	1508
287	1752
288	1668
289	1659
290	1852
291	1981
292	1999
293	1904
294	1813
295	1986
296	2154
297	2369
298	2609
299	2788
300	2916
301	2737
302	2415
303	2348
304	2286
305	2189
306	2301
307	2669
308	2642
309	2605
310	2433
311	2656
312	2747
313	2727
314	2807
315	3056
316	3245
317	3773
318	3743
319	3535
320	3151
321	2983
322	3074
323	3299
324	3639
325	4051
326	4159
327	3872
328	3376
329	3225
330	3490
331	3573
332	3581
333	3410
334	3288
335	3431
336	3471
337	3494
338	3589
339	3629
340	3369
341	3238
342	2968
343	2861
344	2624
345	2654
346	2933
347	3456
348	3629
349	3626
350	3504
351	3155
352	2805
353	2906
354	3008
355	3135
356	2814
357	2394
358	2252
359	2237
360	2365
361	2354
362	2271
363	2322
364	2373
365	2538
366	2780
367	2762
368	2473
369	2256
370	2151
371	2005
372	2170
373	2412
374	2572
375	2626
376	2438
377	2108
378	1996
379	2228
380	2425
381	2481
382	2183
383	2082
384	2279
385	2437
386	2358
387	2026
388	1942
389	2000
390	2076
391	2098
392	2252
393	2458
394	2476
395	2469
396	2500
397	2546
398	2918
399	3054
400	2975
401	3164
402	3127
403	2909
404	2503
405	2471
406	2669
407	2740
408	2905
409	3041
410	3293
411	3285
412	3493
413	3623
414	3495
415	3522
416	3601
417	4120
418	4281
419	4125
420	3960
421	3900
422	3823
423	3902
424	4113
425	4233
426	4399
427	4531
428	4218
429	3683
430	3649
431	3808
432	3453
433	3287
434	3542
435	3509
436	3235
437	2751
438	2734
439	2868
440	2877
441	2946
442	3089
443	3250
444	3337
445	3194
446	2818
447	2629
448	2645
449	3267
450	3219
451	3055
452	2849
453	2991
454	3000
455	2875
456	2834
457	2915
458	3669
459	4191
460	3966
461	3679
462	3478
463	3760
464	4010
465	4266
466	4273
467	4417
468	4303
469	5002
470	5425
471	5839
472	5551
473	5722
474	5808
475	6237
476	6589
477	7078
478	7094
479	7362
480	8135
481	8969
482	9820
483	9955
484	9468
485	8950
486	8591
487	8230
488	7824
489	7455
490	7154
491	7076
492	7194
493	7123
494	6795
495	6994
496	7331
497	7716
498	7224
499	6409
500	6185
501	6238
502	6440
503	6561
504	7143
505	7876
506	8269
507	7985
508	8154
509	9032
510	10014
511	10758
512	11362
513	11988
514	12256
515	12079
516	12396
517	12917
518	13754
519	14014
520	13823
521	13552
522	13660
523	13446
524	13330
525	13196
526	13935
527	15530
528	16391
529	16580
530	16455
531	16784
532	17698
533	19357
534	20629
535	23037
536	26179
537	28592
538	29977
539	29891
540	30101
541	32030
542	32840
543	29953
544	26283
545	24442
546	24043
547	22761
548	20029
549	17563
550	16747
551	15991
552	14590
553	13845
554	13635
555	13461
556	12663
557	12090
558	12110
559	12434
560	12750
561	12821
562	13532
563	14155
564	14815
565	14971
566	15789
567	17366
568	18733
569	18799
570	19488
571	20757
572	22828
573	24222
574	25103
575	26785
576	28111
577	28641
578	29333
579	30579
580	31963
581	31925
582	31163
583	29860
584	28173
585	26803
586	25887
587	24034
588	20897
589	18331
590	17187
591	16437
592	15330
593	13435
594	11848
595	11106
596	10831
597	10233
598	9220
599	8862
600	8518
601	7612
602	6761
603	6330
604	6318
605	6585
606	6471
607	5281
608	4659
609	4792
610	4582
611	4615
612	4444
613	4643
614	5127
615	5263
616	5049
617	4877
618	5035
619	5556
620	5880
621	5499
622	4979
623	4366
624	3659
625	3476
626	3560
627	3492
628	3627
629	3673
630	3894
631	4197
632	3861
633	3599
634	3451
635	3582
636	3649
637	3638
638	3611
639	3871
640	4195
641	4282
642	4514
643	5014
644	5072
645	5349
646	5873
647	6331
648	6854
649	6978
650	6675
651	7103
652	8168
653	7636
654	7196
655	7157
656	6899
657	6278
658	5848
659	5778
660	5890
661	5699
662	5648
663	5547
664	5116
665	4573
666	4663
667	4514
668	4126
669	3729
670	3535
671	3066
672	3101
673	3817
674	4028
675	3982
676	3935
677	3721
678	3533
679	3476
680	3492
681	3698
682	3790
683	3617
684	3988
685	3913
686	3151
687	2995
688	3112
689	3241
690	3314
691	3350
692	3100
693	2623
694	2535
695	2827
696	3267
697	2897
698	2478
699	2092
700	1962
701	2278
702	2538
703	2437
704	2465
705	2853
706	3095
707	2882
708	2640
709	2376
710	2736
711	3136
712	3094
713	2842
714	2668
715	2520
716	2819
717	3661
718	4119
719	4137
720	3825
721	3654
722	3885
723	3759
724	3779
725	3849
726	3820
727	3671
728	3717
729	3607
730	3472
731	4127
732	4022
733	3755
734	4017
735	4460
736	4477
737	4600
738	4630
739	4636
740	4597
741	3804
742	3294
743	2708
744	2257
745	2356
746	2707
747	2745
748	2602
749	2320
750	1951
751	2035
752	2235
753	2479
754	2466
755	2269
756	2310
757	2189
758	1901
759	1780
760	1802
761	1740
762	1868
763	1597
764	1789
765	2099
766	2412
767	2864
768	2995
769	2764
770	2890
771	2793
772	2717
773	2259
774	2539
775	2501
776	2340
777	2261
778	1883
779	1795
780	1893
781	2396
782	2529
783	2199
784	2097
785	1862
786	2134
787	2342
788	2005
789	1887
790	2184
791	2362
792	2211
793	2526
794	2415
795	2422
796	2214
797	1778
798	1899
799	2254
800	2197
801	2429
802	2265
803	2019
804	1809
805	1767
806	2222
807	2214
808	2316
809	2817
810	2751
811	2722
812	2762
813	2888
814	2929
815	3072
816	3122
817	2369
818	2182
819	1916
820	1554
821	1798
822	2066
823	2303
824	2588
825	2676
826	2476
827	2770
828	2498
829	2034
830	1728
831	1558
832	1701
833	1833
834	1840
835	2136
836	1772
837	1774
838	1809
839	1639
840	1799
841	2075
842	1745
843	1635
844	2007
845	2435
846	2208
847	2187
848	1973
849	1431
850	1485
851	1627
852	1948
853	2122
854	1998
855	1914
856	2048
857	2166
858	2659
859	2535
860	1875
861	1708
862	1793
863	1568
864	1676
865	1805
866	1724
867	1867
868	2180
869	1685
870	1848
871	2673
872	2828
873	2659
874	2469
875	2336
876	2483
877	2153
878	2432
879	2659
880	2424
881	2491
882	2494
883	2088
884	1995
885	2312
886	2443
887	2450
888	2425
889	1819
890	1920
891	2402
892	2273
893	2396
894	2119
895	2365
896	2667
897	2130
898	2293
899	2387
900	2034
901	1486
902	1359
903	1489
904	2295
905	2386
906	1971
907	1927
908	1709
909	1775
910	2279
911	2114
912	2366
913	2638
914	2791
915	2612
916	2377
917	1927
918	2144
919	2984
920	3009
921	2427
922	2382
923	2383
924	2705
925	2553
926	2520
927	2541
928	2502
929	2077
930	1959
931	2004
932	2326
933	2321
934	2084
935	1830
936	2113
937	2532
938	2520
939	2010
940	1624
941	1928
942	2017
943	1693
944	1879
945	2019
946	1972
947	2629
948	2404
949	2058
950	1997
951	1730
952	1806
953	1970
954	2320
955	2244
956	2067
957	2347
958	2011
959	1965
960	1930
961	2660
962	3091
963	2934
964	2390
965	2264
966	3005
967	2696
968	2484
969	2286
970	1999
971	2046
972	1843
973	1854
974	1900
975	1948
976	2045
977	2172
978	2176
979	2046
980	1765
981	1265
982	1370
983	1659
984	1851
985	1737
986	2065
987	2399
988	2286
989	2104
990	2122
991	2291
992	2340
993	1953
994	2428
995	2835
996	2701
997	2161
998	1889
999	2023
1000	1392
1001	1781
1002	1839
1003	1975
1004	2508
1005	2571
1006	1912
1007	2281
1008	2862
1009	2240
1010	2153
1011	3022
1012	3171
1013	3156
1014	2749
1015	2026
1016	1811
1017	2286
1018	2542
1019	2908
1020	2844
1021	2694
1022	2654
1023	1792
1024	1848