1	1872
2	1951
3	1975
4	1883
5	1764
6	1671
7	1709
8	1842
9	1926
10	1900
11	1849
12	1726
13	1839
14	1753
15	1901
16	1860
17	2015
18	1976
19	1863
20	1845
21	1861
22	1780
23	1840
24	1784
25	1782
26	1698
27	1634
28	1875
29	1909
30	2007
31	2073
32	1970
33	1811
34	1682
35	1719
36	1554
37	1667
38	1679
39	1744
40	1900
41	2019
42	2041
43	1931
44	1826
45	2004
46	1789
47	1882
48	1885
49	2124
50	2045
51	2184
52	2089
53	2113
54	2056
55	1997
56	2003
57	2369
58	2486
59	2468
60	2506
61	2370
62	2472
63	2463
64	2534
65	2541
66	2687
67	2638
68	2552
69	2370
70	2408
71	2206
72	2072
73	2139
74	2238
75	2346
76	2274
77	2106
78	2174
79	2114
80	2353
81	2671
82	2878
83	3019
84	2682
85	2701
86	2586
87	2636
88	2619
89	2695
90	2858
91	3163
92	3407
93	3438
94	3664
95	3599
96	3731
97	3820
98	3980
99	4352
100	4741
101	5398
102	6094
103	6451
104	6646
105	6544
106	6557
107	7259
108	8023
109	8815
110	9775
111	10105
112	11123
113	12444
114	14128
115	15869
116	17180
117	18087
118	19015
119	19572
120	20299
121	20567
122	20288
123	19423
124	18233
125	17194
126	16083
127	15195
128	13796
129	12873
130	11725
131	10661
132	9426
133	8041
134	7274
135	6663
136	6342
137	6044
138	5655
139	5420
140	5267
141	5210
142	5042
143	4422
144	4093
145	3659
146	3375
147	3267
148	3444
149	3721
150	3919
151	3886
152	3838
153	3609
154	3517
155	3456
156	3415
157	3100
158	2900
159	2248
160	2198
161	2121
162	2383
163	2562
164	2667
165	2503
166	2344
167	2076
168	2187
169	2229
170	2223
171	2344
172	2462
173	2581
174	2432
175	2605
176	2569
177	2423
178	2419
179	2367
180	2494
181	2457
182	2156
183	2067
184	2097
185	2188
186	2260
187	2365
188	2217
189	2072
190	1989
191	1916
192	2043
193	2189
194	2106
195	2244
196	2085
197	1921
198	1816
199	1949
200	1742
201	1838
202	1846
203	1920
204	1888
205	2090
206	2273
207	2352
208	2590
209	2342
210	2142
211	1953
212	1896
213	1723
214	1911
215	2352
216	2612
217	2705
218	2679
219	2448
220	2071
221	1682
222	1598
223	1431
224	1678
225	1692
226	1785
227	1612
228	1513
229	1481
230	1569
231	1811
232	1818
233	1900
234	1838
235	1655
236	1846
237	2003
238	2121
239	2105
240	2048
241	2065
242	2198
243	2413
244	2365
245	2153
246	2070
247	1979
248	2040
249	2182
250	2160
251	2002
252	1975
253	2016
254	2097
255	1982
256	1860
257	1577
258	1376
259	1382
260	1613
261	1598
262	1802
263	1757
264	1779
265	1649
266	1982
267	2058
268	2282
269	2373
270	2425
271	2386
272	2485
273	2398
274	2123
275	1999
276	1899
277	2230
278	2470
279	2499
280	2437
281	2189
282	2238
283	2350
284	2511
285	2535
286	2604
287	2377
288	2130
289	2052
290	2132
291	2345
292	2626
293	2760
294	2876
295	2765
296	2905
297	2818
298	2711
299	3017
300	3172
301	3147
302	2947
303	2944
304	2768
305	2674
306	2335
307	2298
308	2483
309	2994
310	3368
311	3503
312	3601
313	3870
314	4357
315	4459
316	4660
317	4926
318	5259
319	5726
320	6049
321	6303
322	6732
323	7434
324	7884
325	8058
326	7914
327	7920
328	7582
329	6851
330	6267
331	5679
332	5037
333	4713
334	4619
335	4648
336	4611
337	4360
338	3981
339	3854
340	3609
341	3710
342	3884
343	3704
344	4004
345	4206
346	4553
347	5070
348	5406
349	5100
350	4593
351	4323
352	4288
353	4259
354	4326
355	4378
356	4388
357	4302
358	4226
359	3662
360	3612
361	3432
362	3693
363	3736
364	3557
365	3204
366	2652
367	2581
368	2726
369	3103
370	3105
371	3113
372	2999
373	3199
374	3151
375	2886
376	2777
377	2841
378	2948
379	2906
380	3017
381	3230
382	3186
383	3023
384	2961
385	3181
386	3252
387	3299
388	3359
389	3185
390	3034
391	3219
392	3412
393	3438
394	3253
395	3390
396	3855
397	3955
398	4369
399	4649
400	4573
401	4309
402	4076
403	3986
404	4089
405	3986
406	3869
407	3839
408	4271
409	5120
410	5775
411	5635
412	5668
413	5781
414	6018
415	6544
416	6999
417	7148
418	7043
419	7309
420	7626
421	8432
422	8766
423	8828
424	8111
425	7552
426	7401
427	7670
428	7709
429	7767
430	7193
431	6687
432	6398
433	6210
434	6355
435	6446
436	6084
437	5691
438	4890
439	4872
440	5259
441	5008
442	4625
443	4525
444	4755
445	4697
446	4582
447	4390
448	4735
449	5167
450	5930
451	6010
452	6083
453	5541
454	5209
455	5324
456	6137
457	6467
458	6533
459	6659
460	6560
461	6788
462	7046
463	8163
464	9575
465	10538
466	10877
467	11269
468	11379
469	12020
470	12499
471	13988
472	14470
473	14977
474	15383
475	16383
476	16992
477	18027
478	18607
479	19256
480	19808
481	21091
482	21980
483	22362
484	22512
485	22223
486	22041
487	20474
488	19212
489	18103
490	16825
491	16351
492	16274
493	16072
494	15579
495	15448
496	15198
497	14927
498	15498
499	15184
500	15153
501	15571
502	16607
503	17719
504	18454
505	19116
506	20054
507	21059
508	22002
509	23984
510	26324
511	27976
512	29200
513	30453
514	31769
515	34008
516	36473
517	37901
518	38060
519	37517
520	36216
521	34850
522	35477
523	36792
524	37255
525	37476
526	38265
527	40158
528	41727
529	43305
530	45791
531	48347
532	51519
533	54983
534	59091
535	63724
536	68988
537	73018
538	77044
539	79397
540	81921
541	84193
542	84965
543	82942
544	79611
545	77055
546	72699
547	65876
548	59646
549	54441
550	51670
551	49663
552	46166
553	42326
554	39500
555	37284
556	35687
557	34287
558	33435
559	33603
560	34877
561	36052
562	36836
563	38393
564	40998
565	42258
566	44347
567	46721
568	47566
569	48652
570	51101
571	55042
572	59877
573	64383
574	68807
575	73693
576	77609
577	81516
578	84116
579	86590
580	89278
581	89168
582	87399
583	83890
584	80715
585	78354
586	74582
587	69327
588	63064
589	57056
590	51989
591	45289
592	40005
593	36322
594	34015
595	31738
596	29293
597	26302
598	23711
599	22289
600	21615
601	21413
602	20071
603	19082
604	17773
605	16695
606	15739
607	15014
608	14424
609	13698
610	13192
611	12560
612	12118
613	11341
614	10630
615	9880
616	9686
617	9196
618	9256
619	9268
620	9305
621	9739
622	9562
623	9214
624	8783
625	8755
626	9145
627	9147
628	8523
629	7751
630	7853
631	7948
632	8026
633	8377
634	8479
635	8844
636	9430
637	9317
638	8800
639	8857
640	8957
641	9760
642	10761
643	11640
644	11672
645	12472
646	13092
647	13106
648	13715
649	14608
650	15859
651	16849
652	17008
653	16630
654	16474
655	17800
656	18579
657	18135
658	16872
659	15764
660	14466
661	13863
662	13037
663	11804
664	11079
665	11121
666	10653
667	10367
668	9204
669	8478
670	8790
671	8764
672	7762
673	6899
674	6530
675	6318
676	6573
677	6447
678	6376
679	6425
680	6111
681	5896
682	6225
683	6440
684	6210
685	5719
686	5073
687	5106
688	5474
689	5364
690	5746
691	5581
692	5170
693	4737
694	4662
695	4770
696	4932
697	5207
698	5081
699	4242
700	4015
701	3791
702	3923
703	3753
704	3550
705	3723
706	4181
707	3768
708	3622
709	3937
710	3953
711	3701
712	4069
713	4005
714	3428
715	3624
716	4267
717	4839
718	5528
719	5427
720	5663
721	5670
722	5840
723	5894
724	5575
725	5743
726	6365
727	6321
728	6418
729	6619
730	7084
731	6795
732	6584
733	6157
734	5505
735	4891
736	5261
737	5819
738	5938
739	5166
740	4792
741	4464
742	4090
743	3690
744	3616
745	3227
746	3048
747	3092
748	3447
749	3404
750	3157
751	3152
752	3079
753	2784
754	2670
755	3064
756	3193
757	2976
758	2368
759	2310
760	2342
761	2266
762	2180
763	2260
764	2258
765	2365
766	2203
767	2255
768	2666
769	2711
770	2726
771	2956
772	2803
773	2957
774	2611
775	2907
776	2792
777	2446
778	2149
779	2322
780	2652
781	2469
782	2211
783	2216
784	2078
785	2074
786	1763
787	1871
788	2360
789	2573
790	2533
791	2264
792	2208
793	1878
794	1298
795	1352
796	1875
797	1852
798	1698
799	1898
800	1861
801	1850
802	2086
803	2502
804	2588
805	2697
806	2728
807	2863
808	2730
809	2987
810	2710
811	2289
812	2002
813	2202
814	2514
815	2782
816	3002
817	2942
818	2530
819	1915
820	1834
821	1867
822	2177
823	1918
824	1956
825	2228
826	2327
827	2048
828	1659
829	1958
830	2060
831	1963
832	1970
833	2317
834	2092
835	1787
836	1669
837	1888
838	2126
839	1817
840	2126
841	2028
842	1794
843	1912
844	2068
845	2117
846	1780
847	1690
848	1739
849	1836
850	1891
851	2198
852	2235
853	2488
854	2615
855	2073
856	1672
857	1476
858	1842
859	1757
860	1645
861	1540
862	1821
863	1486
864	1579
865	1579
866	1270
867	1543
868	2079
869	2185
870	1686
871	1906
872	2139
873	2379
874	2485
875	2540
876	2131
877	1903
878	2044
879	2112
880	1907
881	1810
882	1995
883	1705
884	1751
885	1955
886	2302
887	1942
888	1771
889	1528
890	1714
891	1540
892	1498
893	1615
894	1392
895	1516
896	2273
897	2517
898	2658
899	2744
900	2549
901	2326
902	2279
903	2033
904	2303
905	2549
906	2413
907	2647
908	2863
909	2533
910	2648
911	2442
912	2091
913	1910
914	1877
915	1563
916	1490
917	1457
918	1706
919	2080
920	1923
921	1816
922	1756
923	1788
924	1947
925	2024
926	2510
927	2645
928	2110
929	1881
930	2087
931	1962
932	1781
933	1819
934	1757
935	2168
936	2015
937	2126
938	1862
939	2024
940	1803
941	1803
942	2232
943	1568
944	1701
945	1651
946	1463
947	1471
948	1440
949	1547
950	1893
951	2083
952	1629
953	1701
954	1789
955	2274
956	2852
957	3156
958	2669
959	2116
960	2346
961	2189
962	2068
963	2216
964	1876
965	1568
966	1304
967	1275
968	1510
969	1576
970	1832
971	1829
972	1415
973	1729
974	1778
975	2264
976	2015
977	1762
978	1537
979	1340
980	1470
981	1675
982	1891
983	1955
984	1471
985	1766
986	1917
987	2553
988	2308
989	2362
990	2141
991	2560
992	2179
993	1997
994	2065
995	2120
996	2027
997	1405
998	1205
999	1243
1000	1433
1001	1653
1002	1583
1003	1565
1004	1101
1005	1176
1006	1800
1007	1910
1008	1505
1009	1974
1010	2427
1011	2427
1012	1902
1013	1723
1014	2440
1015	2757
1016	2328
1017	2039
1018	1670
1019	2173
1020	3032
1021	2866
1022	2127
1023	1680
1024	1873