1	2119
2	2064
3	1928
4	1992
5	1970
6	1761
7	1785
8	1862
9	1892
10	1898
11	2253
12	2198
13	2278
14	2322
15	2288
16	2401
17	2323
18	2243
19	2427
20	2312
21	2367
22	2264
23	2252
24	2231
25	2289
26	2190
27	2139
28	1896
29	1961
30	1896
31	1977
32	2173
33	2188
34	2029
35	1940
36	1934
37	2102
38	2180
39	2286
40	2298
41	2500
42	2384
43	2345
44	2376
45	2470
46	2564
47	2387
48	2468
49	2455
50	2314
51	2074
52	2112
53	2107
54	2442
55	2682
56	2742
57	2691
58	2385
59	2259
60	1941
61	1837
62	1683
63	1913
64	1930
65	2003
66	1957
67	1860
68	1851
69	1830
70	1930
71	2082
72	2142
73	2297
74	2495
75	2681
76	2786
77	2892
78	2640
79	2450
80	2209
81	2253
82	2335
83	2255
84	2115
85	2280
86	2347
87	2299
88	2221
89	2132
90	2236
91	2325
92	2623
93	2709
94	2921
95	3071
96	3103
97	2910
98	2771
99	2593
100	2596
101	2506
102	2606
103	2782
104	2953
105	3311
106	3527
107	3818
108	3925
109	4073
110	4272
111	4781
112	5352
113	5704
114	6144
115	6345
116	6538
117	6837
118	6622
119	6673
120	6478
121	6314
122	6162
123	6038
124	6014
125	5704
126	5201
127	4607
128	4492
129	4292
130	4381
131	4076
132	3994
133	3776
134	3537
135	3336
136	3232
137	3092
138	2820
139	2866
140	2748
141	2796
142	2973
143	3046
144	2863
145	2752
146	2675
147	2660
148	2950
149	3067
150	2918
151	2746
152	2605
153	2226
154	2324
155	2241
156	2315
157	2207
158	2159
159	1997
160	2116
161	2236
162	2572
163	2562
164	2656
165	2270
166	2145
167	1834
168	1656
169	1612
170	1434
171	1478
172	1670
173	1833
174	2061
175	2232
176	2476
177	2517
178	2721
179	2630
180	2675
181	2528
182	2563
183	2313
184	2175
185	1948
186	1898
187	2034
188	2058
189	2417
190	2283
191	2350
192	2506
193	2560
194	2455
195	2366
196	2303
197	2142
198	1933
199	1647
200	1703
201	1557
202	1463
203	1428
204	1581
205	1573
206	1825
207	1814
208	1977
209	1786
210	1784
211	1911
212	2122
213	2061
214	2116
215	2240
216	2124
217	2165
218	2105
219	1983
220	2061
221	2124
222	1997
223	1866
224	1954
225	1961
226	2148
227	2218
228	2143
229	1859
230	1842
231	1768
232	1917
233	2037
234	2051
235	1958
236	1920
237	1954
238	1861
239	1602
240	1605
241	1607
242	1764
243	2044
244	2128
245	2188
246	2115
247	1979
248	2043
249	2099
250	2188
251	2160
252	2251
253	1904
254	1637
255	1727
256	1866
257	2264
258	2338
259	2303
260	2288
261	2149
262	2044
263	2161
264	2440
265	2330
266	2071
267	1952
268	1935
269	2163
270	2213
271	2375
272	2436
273	2500
274	2213
275	1968
276	1867
277	2109
278	2417
279	2322
280	2295
281	2070
282	2222
283	2275
284	2307
285	2291
286	2022
287	1947
288	2070
289	2291
290	2457
291	2533
292	2208
293	2336
294	2310
295	1983
296	1918
297	1782
298	1909
299	2113
300	2241
301	2319
302	2465
303	2471
304	2682
305	2712
306	2721
307	2724
308	2247
309	2101
310	2047
311	1945
312	1919
313	2109
314	2019
315	1834
316	2114
317	2325
318	2371
319	2301
320	2347
321	2533
322	2860
323	3156
324	3386
325	3393
326	3555
327	3351
328	3200
329	3412
330	3562
331	3490
332	3011
333	2847
334	2570
335	2442
336	2340
337	2499
338	2511
339	2552
340	2560
341	2734
342	2614
343	2554
344	2336
345	2449
346	2966
347	3355
348	3063
349	2694
350	2341
351	2359
352	2595
353	2846
354	2806
355	2736
356	2524
357	2365
358	2423
359	2549
360	2517
361	2287
362	2211
363	2256
364	2305
365	2356
366	2395
367	2218
368	1806
369	1808
370	1946
371	2102
372	2317
373	2319
374	2341
375	2268
376	2039
377	1972
378	2220
379	2313
380	2226
381	2171
382	2238
383	2321
384	2468
385	2401
386	2177
387	1864
388	1664
389	1614
390	1669
391	1708
392	1909
393	2124
394	2273
395	2339
396	2094
397	2049
398	2204
399	2406
400	2542
401	2742
402	2728
403	2656
404	2408
405	2562
406	2605
407	2574
408	2426
409	2404
410	2370
411	2389
412	2543
413	2753
414	2807
415	3022
416	3227
417	3395
418	3440
419	3392
420	3086
421	3233
422	3275
423	3194
424	3240
425	3272
426	3359
427	3449
428	3319
429	3133
430	2941
431	2573
432	2272
433	1970
434	1861
435	1783
436	1995
437	2189
438	2604
439	2766
440	2402
441	2264
442	2360
443	2627
444	3111
445	3444
446	3207
447	2894
448	2811
449	2864
450	2602
451	2290
452	1978
453	2038
454	2071
455	2205
456	2409
457	2617
458	2961
459	3534
460	3563
461	4034
462	4389
463	3963
464	3544
465	3620
466	3754
467	3964
468	4009
469	3972
470	3870
471	3679
472	3809
473	4201
474	4584
475	4920
476	5323
477	5512
478	5493
479	5991
480	6374
481	6438
482	6724
483	6858
484	6582
485	6257
486	6025
487	5962
488	5743
489	5629
490	5288
491	4999
492	4618
493	4846
494	5010
495	5214
496	5601
497	5424
498	5130
499	5167
500	5462
501	5233
502	5083
503	5464
504	5901
505	6392
506	7008
507	7346
508	7389
509	7594
510	7754
511	7642
512	7164
513	7526
514	8059
515	8934
516	9669
517	9709
518	9680
519	9362
520	9409
521	9788
522	10179
523	9818
524	9093
525	8805
526	8984
527	9822
528	10786
529	11977
530	12410
531	12935
532	14177
533	14834
534	15166
535	16086
536	17860
537	19403
538	20525
539	20554
540	20465
541	20342
542	20214
543	20120
544	19501
545	18927
546	17880
547	16930
548	15455
549	13810
550	12828
551	11962
552	10809
553	10180
554	10107
555	9829
556	9364
557	9226
558	9320
559	9315
560	9633
561	9596
562	9346
563	9861
564	10957
565	11801
566	12199
567	11885
568	12122
569	12210
570	13623
571	14610
572	15144
573	15980
574	17240
575	18579
576	19990
577	21231
578	22136
579	21893
580	21652
581	21468
582	22000
583	21574
584	20274
585	20700
586	20242
587	18569
588	16041
589	13311
590	12010
591	11378
592	10239
593	8734
594	8241
595	7531
596	7130
597	6898
598	6644
599	6125
600	5304
601	4628
602	4773
603	4803
604	4304
605	4179
606	4463
607	4823
608	4817
609	4338
610	4107
611	3693
612	3417
613	3770
614	3665
615	3711
616	4098
617	4464
618	4581
619	4301
620	3979
621	4169
622	4136
623	3811
624	3619
625	3604
626	3746
627	4165
628	4094
629	3766
630	3492
631	3079
632	2904
633	3065
634	3208
635	3132
636	3228
637	3435
638	3522
639	3725
640	4009
641	3843
642	3456
643	3805
644	4464
645	4688
646	4368
647	4576
648	5416
649	5547
650	5258
651	4988
652	5023
653	5435
654	5201
655	4822
656	4489
657	4148
658	4633
659	4664
660	3933
661	3547
662	3673
663	3742
664	3380
665	3651
666	4375
667	4309
668	4030
669	4076
670	4020
671	3315
672	3021
673	3184
674	3179
675	2959
676	3021
677	3078
678	3106
679	2857
680	3002
681	3578
682	3634
683	2992
684	2760
685	2820
686	2491
687	2363
688	2562
689	2782
690	2616
691	2349
692	2371
693	2449
694	2662
695	2384
696	2293
697	2303
698	2382
699	2498
700	2439
701	2545
702	2257
703	2039
704	2247
705	2644
706	2592
707	2511
708	2325
709	2344
710	2351
711	2347
712	3055
713	3119
714	2833
715	2368
716	2342
717	2761
718	3169
719	2957
720	2616
721	2536
722	2861
723	3177
724	2712
725	2761
726	3180
727	2963
728	2793
729	3089
730	3492
731	3779
732	3952
733	3918
734	3306
735	2737
736	3100
737	4036
738	3970
739	3597
740	3000
741	2727
742	3070
743	3318
744	3165
745	2758
746	2813
747	3059
748	3255
749	2873
750	2334
751	2522
752	2536
753	2381
754	2641
755	2458
756	2550
757	2391
758	2098
759	2098
760	2003
761	1906
762	1920
763	1979
764	1952
765	1917
766	1967
767	2104
768	2224
769	2152
770	2245
771	2087
772	1937
773	2234
774	2593
775	2580
776	2526
777	2307
778	2038
779	1999
780	2194
781	2321
782	2114
783	1885
784	2084
785	2131
786	1975
787	2015
788	2293
789	2348
790	2314
791	2221
792	1871
793	2136
794	2147
795	2211
796	1631
797	1715
798	1642
799	1717
800	1646
801	1762
802	1905
803	2376
804	2389
805	1991
806	2239
807	1895
808	2265
809	2342
810	2197
811	2327
812	2462
813	2427
814	2250
815	2144
816	2237
817	2098
818	1730
819	1470
820	1584
821	1753
822	2045
823	2051
824	1876
825	1914
826	1617
827	1934
828	2021
829	1717
830	1714
831	2037
832	2215
833	2283
834	2149
835	1833
836	1907
837	2511
838	2408
839	1843
840	1990
841	2449
842	2208
843	1819
844	1841
845	2241
846	2512
847	2383
848	2125
849	2071
850	1992
851	2260
852	1828
853	1883
854	2108
855	1901
856	1733
857	1802
858	2014
859	2550
860	2391
861	2415
862	2408
863	1951
864	1741
865	2181
866	2477
867	2642
868	2206
869	1929
870	1886
871	2211
872	2022
873	2212
874	2169
875	1945
876	2099
877	2044
878	2010
879	1986
880	2317
881	2390
882	2509
883	2886
884	2548
885	2348
886	2143
887	1985
888	1828
889	1686
890	2110
891	2283
892	2209
893	2413
894	2099
895	2072
896	2155
897	1683
898	1781
899	2265
900	2404
901	1922
902	1945
903	2216
904	2435
905	2538
906	2400
907	2497
908	2314
909	2391
910	2644
911	2891
912	2685
913	2289
914	2085
915	2037
916	2024
917	2239
918	2328
919	2366
920	1994
921	1847
922	1872
923	2001
924	2283
925	1991
926	1932
927	2525
928	2782
929	1761
930	1543
931	1809
932	2112
933	2412
934	2337
935	2174
936	1688
937	1653
938	1711
939	1802
940	1649
941	1476
942	1561
943	2134
944	2561
945	2373
946	1984
947	1939
948	1545
949	1594
950	1461
951	2141
952	2400
953	2403
954	2086
955	1707
956	2072
957	1980
958	1813
959	1923
960	1612
961	1692
962	2096
963	2574
964	2349
965	1972
966	2373
967	3021
968	3012
969	2860
970	2340
971	2162
972	2212
973	2019
974	1646
975	1583
976	1855
977	1912
978	2220
979	1905
980	1923
981	2454
982	2075
983	2406
984	2691
985	2080
986	2295
987	2348
988	2385
989	2562
990	2558
991	2713
992	2483
993	1728
994	1309
995	2069
996	2897
997	2436
998	2255
999	2129
1000	1888
1001	2025
1002	2651
1003	2334
1004	1733
1005	1821
1006	1971
1007	2391
1008	2277
1009	1933
1010	1863
1011	2446
1012	2534
1013	2282
1014	2754
1015	2554
1016	1844
1017	1881
1018	1730
1019	2212
1020	2303
1021	2320
1022	1987
1023	2081
1024	2481