1	1553
2	1580
3	1414
4	1329
5	1258
6	1210
7	1316
8	1621
9	1802
10	1862
11	1945
12	1714
13	1805
14	1697
15	1729
16	1751
17	1554
18	1540
19	1502
20	1537
21	1573
22	1693
23	2052
24	2041
25	2110
26	1747
27	1575
28	1666
29	1686
30	1599
31	1668
32	1452
33	1396
34	1429
35	1465
36	1592
37	1683
38	1609
39	1853
40	1930
41	1954
42	2016
43	1855
44	1857
45	1991
46	2161
47	2088
48	2106
49	2103
50	1970
51	1829
52	1702
53	1921
54	1973
55	2162
56	2299
57	2404
58	2256
59	2356
60	2418
61	2499
62	2661
63	2643
64	2486
65	2204
66	2137
67	1908
68	1787
69	1685
70	1807
71	2055
72	2097
73	2309
74	2367
75	2476
76	2318
77	2223
78	2179
79	2360
80	2597
81	2709
82	2864
83	3013
84	3076
85	3186
86	2909
87	2790
88	2714
89	2619
90	2708
91	2792
92	2730
93	2555
94	2413
95	2518
96	2724
97	2914
98	3144
99	3281
100	3354
101	3469
102	3492
103	3893
104	4081
105	4537
106	4664
107	5113
108	5766
109	6442
110	7411
111	8426
112	8988
113	9406
114	9786
115	10006
116	10793
117	12017
118	12608
119	12700
120	12732
121	12990
122	12965
123	12426
124	11042
125	10097
126	9277
127	8494
128	7729
129	7036
130	6494
131	5988
132	5622
133	5090
134	4678
135	4391
136	4398
137	4388
138	4354
139	4053
140	3792
141	3395
142	2953
143	2570
144	2552
145	2451
146	2582
147	2653
148	2677
149	2708
150	2680
151	2661
152	2764
153	2851
154	2860
155	2641
156	2339
157	2044
158	2037
159	2042
160	2282
161	2311
162	2450
163	2562
164	2469
165	2334
166	2419
167	2354
168	2343
169	2136
170	1834
171	1939
172	2326
173	2586
174	2507
175	2297
176	1983
177	1795
178	1658
179	1715
180	2089
181	2222
182	2099
183	1803
184	1692
185	1822
186	1875
187	1895
188	1770
189	1636
190	1595
191	1522
192	1651
193	1842
194	1964
195	1972
196	1832
197	1744
198	1790
199	1883
200	1812
201	1915
202	1885
203	1749
204	1529
205	1543
206	1601
207	1586
208	1771
209	1749
210	1824
211	1684
212	1718
213	1727
214	1675
215	1605
216	1625
217	1625
218	1552
219	1668
220	1761
221	1753
222	1896
223	1918
224	2104
225	1962
226	1903
227	1677
228	1623
229	1779
230	1910
231	1930
232	1978
233	2042
234	1924
235	1904
236	1784
237	1623
238	1453
239	1485
240	1607
241	1914
242	2187
243	2254
244	2214
245	2208
246	2176
247	2071
248	2157
249	2420
250	2491
251	2376
252	2473
253	2141
254	1880
255	1718
256	1716
257	1764
258	1624
259	1798
260	1827
261	1802
262	1905
263	1868
264	1900
265	1875
266	2169
267	2302
268	2358
269	2321
270	1936
271	1711
272	1811
273	1880
274	1763
275	1780
276	1781
277	1802
278	1818
279	1728
280	1752
281	1639
282	1897
283	1980
284	2339
285	2371
286	2607
287	2705
288	2495
289	2286
290	2051
291	1806
292	2057
293	2124
294	2063
295	1968
296	2203
297	2040
298	1982
299	1968
300	2086
301	2125
302	2142
303	2128
304	2001
305	1936
306	2195
307	2545
308	2510
309	2615
310	2583
311	2452
312	2710
313	3163
314	3539
315	3683
316	3620
317	3833
318	4009
319	4332
320	4651
321	4736
322	4752
323	4979
324	5028
325	4987
326	5023
327	4946
328	4688
329	4460
330	4177
331	4138
332	4000
333	4053
334	3795
335	3605
336	3429
337	2788
338	2619
339	2707
340	2673
341	3038
342	3368
343	3402
344	3442
345	3459
346	3545
347	3888
348	4050
349	4070
350	3872
351	3622
352	3674
353	3409
354	3435
355	3361
356	3451
357	3202
358	3079
359	2592
360	2476
361	2317
362	2534
363	2419
364	2402
365	2242
366	2238
367	2338
368	2410
369	2281
370	2079
371	2560
372	2725
373	2795
374	2584
375	2537
376	2868
377	3058
378	3144
379	2631
380	2459
381	2667
382	2846
383	2707
384	2636
385	2454
386	2089
387	1871
388	1919
389	1931
390	2277
391	2681
392	2791
393	2784
394	2585
395	2693
396	3250
397	3537
398	3497
399	3263
400	3257
401	3434
402	3520
403	3114
404	2795
405	2715
406	3044
407	2868
408	2980
409	3212
410	3507
411	3538
412	3443
413	3737
414	3995
415	4500
416	4524
417	4636
418	4564
419	5066
420	5345
421	5406
422	5329
423	5518
424	5494
425	5313
426	5340
427	5200
428	5136
429	4916
430	5229
431	5234
432	5035
433	4692
434	4288
435	3835
436	3606
437	3605
438	3527
439	3544
440	3624
441	3163
442	3190
443	3505
444	3763
445	3974
446	4019
447	3841
448	3906
449	3950
450	3504
451	3120
452	3065
453	2982
454	3207
455	3537
456	4130
457	4439
458	4506
459	4954
460	5366
461	5940
462	5968
463	5737
464	5664
465	5275
466	5467
467	5979
468	6536
469	7551
470	8119
471	8703
472	8990
473	8921
474	9168
475	9513
476	10113
477	10623
478	11168
479	11873
480	12756
481	14121
482	14878
483	14865
484	14891
485	14468
486	13952
487	13364
488	12786
489	12200
490	11559
491	10814
492	9814
493	9873
494	10061
495	9985
496	9729
497	9657
498	10048
499	9817
500	9902
501	10071
502	10378
503	10655
504	10959
505	11776
506	12915
507	13901
508	15481
509	16903
510	17854
511	18302
512	18830
513	19946
514	21309
515	21744
516	21752
517	20789
518	21344
519	22107
520	22002
521	21840
522	23204
523	23534
524	23246
525	23766
526	24324
527	24944
528	25894
529	26744
530	27726
531	29879
532	31457
533	32801
534	34355
535	37029
536	41866
537	46658
538	50324
539	51205
540	50304
541	50033
542	49043
543	47397
544	44567
545	41741
546	38897
547	35897
548	33471
549	30593
550	28446
551	27653
552	27229
553	26841
554	26339
555	25098
556	24127
557	23339
558	22623
559	22015
560	21291
561	21019
562	21191
563	21091
564	22172
565	23636
566	25193
567	27068
568	28647
569	29388
570	31374
571	34106
572	35878
573	38291
574	40646
575	43835
576	47067
577	49765
578	52384
579	54618
580	55157
581	54224
582	52866
583	50674
584	47915
585	45376
586	41977
587	39117
588	35996
589	33209
590	30112
591	27356
592	24510
593	21997
594	20705
595	19269
596	17694
597	16572
598	15140
599	13635
600	13172
601	12952
602	11495
603	10430
604	9904
605	9331
606	9285
607	8813
608	8539
609	8320
610	8080
611	7485
612	6768
613	6800
614	7041
615	6958
616	6548
617	6047
618	5712
619	5941
620	5910
621	5515
622	5311
623	5551
624	5655
625	5632
626	5350
627	5334
628	5191
629	4686
630	4528
631	5418
632	6077
633	5987
634	5271
635	5296
636	6064
637	6450
638	6069
639	5910
640	5954
641	6266
642	6950
643	7834
644	8086
645	8138
646	8488
647	8790
648	9257
649	9574
650	9704
651	10027
652	10811
653	11005
654	10817
655	10396
656	10169
657	10330
658	9622
659	8687
660	8061
661	7604
662	7373
663	7486
664	7670
665	7231
666	6332
667	5865
668	5940
669	5497
670	5048
671	4357
672	4178
673	3888
674	3818
675	3825
676	3905
677	3736
678	3376
679	3455
680	3673
681	3197
682	2849
683	3073
684	3170
685	3101
686	2993
687	3225
688	3275
689	3354
690	3807
691	3425
692	2926
693	2740
694	2664
695	2858
696	2885
697	2667
698	2352
699	2320
700	2498
701	2427
702	2461
703	2649
704	2763
705	3183
706	3353
707	3056
708	2746
709	2851
710	3383
711	3643
712	3230
713	2749
714	3469
715	4170
716	3949
717	4091
718	3665
719	3437
720	4095
721	4650
722	4627
723	4472
724	4934
725	5485
726	5476
727	5215
728	5020
729	4891
730	4804
731	4574
732	4074
733	3755
734	4205
735	4508
736	3796
737	3465
738	3921
739	4133
740	3874
741	3171
742	2642
743	2913
744	2978
745	2967
746	2896
747	2718
748	2579
749	2417
750	2333
751	2220
752	2309
753	2281
754	2074
755	2451
756	2276
757	2253
758	2096
759	2235
760	2574
761	2401
762	2234
763	2247
764	1879
765	1958
766	2109
767	2067
768	2256
769	2361
770	2551
771	2541
772	2283
773	2292
774	2094
775	2045
776	2014
777	1901
778	1843
779	2223
780	2261
781	1627
782	1156
783	1387
784	1825
785	1921
786	1796
787	1800
788	1889
789	1825
790	1794
791	1876
792	1723
793	1892
794	2153
795	2284
796	2413
797	2687
798	2485
799	1918
800	1595
801	1552
802	1440
803	1231
804	1453
805	1723
806	1670
807	2075
808	2331
809	2034
810	1562
811	1489
812	1910
813	2374
814	2639
815	2546
816	2425
817	2547
818	2294
819	1665
820	1074
821	1013
822	1218
823	1619
824	1807
825	2106
826	2242
827	2247
828	2189
829	2044
830	1495
831	1562
832	1843
833	2016
834	2267
835	2065
836	1800
837	2326
838	2546
839	2244
840	1555
841	1712
842	2131
843	2569
844	2566
845	2022
846	1744
847	1599
848	1583
849	1627
850	1504
851	1582
852	1649
853	1765
854	1898
855	1809
856	1888
857	1761
858	1277
859	1156
860	1436
861	1438
862	1828
863	1944
864	1840
865	1823
866	1771
867	1627
868	1815
869	1737
870	1691
871	1958
872	1906
873	1691
874	1989
875	1905
876	1973
877	1952
878	1913
879	2333
880	2306
881	1761
882	1767
883	1599
884	1797
885	2135
886	1884
887	1434
888	1702
889	1957
890	2180
891	1978
892	1984
893	1721
894	1590
895	1783
896	2041
897	2021
898	2185
899	2336
900	2326
901	1929
902	2165
903	1883
904	1813
905	1983
906	1817
907	1602
908	1878
909	1830
910	1433
911	1233
912	1696
913	2290
914	2264
915	2463
916	1964
917	1831
918	1781
919	1420
920	1476
921	1437
922	1541
923	1523
924	1844
925	2142
926	2325
927	2097
928	2388
929	2476
930	2008
931	2329
932	2504
933	2230
934	1863
935	2007
936	2230
937	2486
938	1999
939	1852
940	1724
941	1963
942	2278
943	2018
944	2023
945	1787
946	1648
947	1953
948	2199
949	1943
950	2100
951	2382
952	2507
953	1974
954	1628
955	1439
956	1708
957	1400
958	1423
959	1465
960	1837
961	1672
962	1836
963	2123
964	2116
965	1866
966	1801
967	1992
968	2142
969	1723
970	1811
971	1762
972	1405
973	1674
974	1757
975	1668
976	1616
977	1466
978	1380
979	1308
980	1762
981	2151
982	2336
983	2114
984	1716
985	2167
986	1947
987	1918
988	2042
989	2108
990	1858
991	1717
992	1743
993	2325
994	2438
995	1678
996	1379
997	1229
998	1318
999	1559
1000	1706
1001	2158
1002	2001
1003	2230
1004	2032
1005	2194
1006	2362
1007	1988
1008	1622
1009	1135
1010	1538
1011	1588
1012	1827
1013	1838
1014	1972
1015	2095
1016	1882
1017	2163
1018	1551
1019	1265
1020	1679
1021	1591
1022	1748
1023	1472
1024	1547