1	1545
2	1653
3	1648
4	1627
5	1522
6	1537
7	1495
8	1677
9	1617
10	1763
11	1718
12	1682
13	1576
14	1631
15	1770
16	1838
17	1868
18	2086
19	2052
20	1962
21	1942
22	1974
23	1958
24	1837
25	1917
26	1830
27	1890
28	1747
29	1504
30	1397
31	1466
32	1448
33	1420
34	1431
35	1533
36	1535
37	1678
38	1682
39	1689
40	1799
41	1753
42	1969
43	1757
44	1865
45	2013
46	2162
47	2037
48	2044
49	2016
50	2091
51	2111
52	2226
53	2109
54	2104
55	1981
56	2033
57	1981
58	1816
59	1745
60	1896
61	1960
62	2276
63	2363
64	2404
65	2246
66	2274
67	2095
68	2071
69	2240
70	2122
71	2243
72	2135
73	2256
74	2138
75	2084
76	2226
77	2321
78	2490
79	2685
80	2775
81	2756
82	2637
83	2551
84	2353
85	2327
86	2350
87	2499
88	2696
89	2712
90	3002
91	3131
92	3342
93	3268
94	3545
95	3219
96	3465
97	3540
98	3559
99	3687
100	3552
101	3619
102	3545
103	3588
104	3784
105	3848
106	4186
107	4180
108	4335
109	4345
110	4543
111	4862
112	4989
113	5156
114	5352
115	5570
116	5759
117	6084
118	6328
119	6323
120	6160
121	6602
122	6519
123	6920
124	6892
125	7207
126	7447
127	7505
128	7347
129	7146
130	6944
131	6866
132	7017
133	6976
134	6717
135	6385
136	5766
137	5689
138	5622
139	5414
140	5324
141	5103
142	4828
143	4820
144	4929
145	4686
146	4568
147	4231
148	4020
149	4119
150	4147
151	4061
152	4259
153	4065
154	3725
155	3498
156	3505
157	3334
158	3447
159	3241
160	3209
161	3068
162	2846
163	2792
164	2963
165	2813
166	2917
167	2966
168	3183
169	3082
170	2821
171	2788
172	2830
173	2737
174	2678
175	2703
176	2584
177	2363
178	2151
179	2031
180	2080
181	2403
182	2105
183	2248
184	2287
185	2268
186	2255
187	2530
188	2389
189	2230
190	2180
191	2054
192	1885
193	1962
194	1934
195	2075
196	2044
197	2192
198	2145
199	2266
200	2212
201	2003
202	1818
203	1904
204	1566
205	1718
206	1860
207	2192
208	2260
209	2227
210	2418
211	2340
212	2135
213	1918
214	1792
215	1667
216	1892
217	1910
218	2146
219	1935
220	2126
221	2282
222	2418
223	2361
224	2292
225	2200
226	2196
227	2120
228	2092
229	1971
230	1998
231	1774
232	2009
233	1982
234	2067
235	2013
236	2046
237	2129
238	1927
239	2004
240	2013
241	1944
242	1990
243	1932
244	1939
245	2007
246	2086
247	2047
248	2071
249	1934
250	1791
251	1930
252	1848
253	2063
254	1965
255	1777
256	1917
257	1923
258	2113
259	2170
260	2027
261	2190
262	2132
263	2206
264	2115
265	2072
266	2060
267	2122
268	2261
269	2221
270	2299
271	2295
272	2321
273	2152
274	2248
275	1994
276	2050
277	2212
278	2331
279	2531
280	2525
281	2456
282	2416
283	2454
284	2374
285	2528
286	2464
287	2498
288	2556
289	2352
290	2425
291	2316
292	2531
293	2472
294	2461
295	2520
296	2525
297	2446
298	2619
299	2558
300	2442
301	2540
302	2699
303	2753
304	2692
305	2830
306	2823
307	2870
308	3173
309	3299
310	3557
311	3391
312	3250
313	3251
314	3216
315	3445
316	3683
317	3605
318	3655
319	3431
320	3709
321	3503
322	3839
323	4258
324	4379
325	4587
326	4174
327	4196
328	3989
329	4074
330	4613
331	4647
332	4400
333	4356
334	4376
335	4272
336	4106
337	4180
338	4127
339	4010
340	3857
341	3938
342	3740
343	3602
344	3518
345	3669
346	3670
347	3962
348	4167
349	4265
350	4361
351	4125
352	4152
353	3983
354	4041
355	4226
356	4293
357	4132
358	4104
359	3986
360	3871
361	3868
362	3827
363	4083
364	4103
365	4270
366	4302
367	4391
368	4293
369	4253
370	3849
371	3934
372	4004
373	3859
374	3716
375	3484
376	3696
377	3859
378	4011
379	3643
380	3489
381	3525
382	3636
383	3383
384	3199
385	3284
386	3591
387	3890
388	4078
389	4019
390	3819
391	3849
392	3839
393	3857
394	3774
395	3362
396	3743
397	3939
398	4181
399	4279
400	4301
401	4597
402	4725
403	4864
404	4581
405	4537
406	4530
407	4678
408	4880
409	5142
410	5181
411	4844
412	4823
413	5094
414	5404
415	5286
416	5237
417	5172
418	5537
419	5745
420	6057
421	5956
422	6029
423	5818
424	5755
425	5565
426	5799
427	5735
428	5944
429	5964
430	6235
431	6628
432	6490
433	6100
434	5777
435	5984
436	6089
437	6192
438	6315
439	6424
440	6218
441	6120
442	6198
443	6150
444	6413
445	6633
446	7023
447	7236
448	7384
449	6841
450	6535
451	6349
452	6380
453	6667
454	6768
455	6808
456	6755
457	6982
458	6999
459	7253
460	7629
461	8364
462	8286
463	8397
464	9077
465	9419
466	9213
467	9344
468	9494
469	9942
470	9985
471	10252
472	10163
473	10512
474	11503
475	12313
476	12698
477	12890
478	13206
479	13824
480	14111
481	14282
482	13944
483	13741
484	14533
485	14980
486	15329
487	15337
488	15101
489	14877
490	15354
491	15380
492	15036
493	15558
494	15851
495	16595
496	16378
497	16109
498	16407
499	16637
500	16410
501	16517
502	16886
503	17314
504	17559
505	18103
506	18342
507	18465
508	18575
509	19087
510	19868
511	20517
512	20905
513	21474
514	21405
515	21651
516	21981
517	22639
518	23664
519	24539
520	25371
521	24959
522	24993
523	25676
524	25875
525	26205
526	27060
527	27976
528	28188
529	29154
530	29763
531	30571
532	31194
533	31984
534	32648
535	33332
536	33789
537	34520
538	35427
539	36034
540	36396
541	37132
542	38295
543	39327
544	39444
545	39783
546	39658
547	38857
548	37687
549	37199
550	37623
551	38787
552	38632
553	38343
554	37527
555	36448
556	35183
557	35918
558	35996
559	35912
560	36102
561	36329
562	36451
563	36380
564	36917
565	36249
566	35276
567	34572
568	34769
569	35032
570	35315
571	34603
572	35063
573	35689
574	36271
575	37774
576	38525
577	38352
578	38464
579	38285
580	38399
581	38288
582	39342
583	39442
584	38761
585	38158
586	37042
587	37400
588	37383
589	36484
590	34671
591	33964
592	33891
593	33330
594	32362
595	30996
596	30404
597	29292
598	28528
599	28000
600	26867
601	26224
602	26017
603	25307
604	24276
605	23651
606	23014
607	21591
608	20098
609	19766
610	20037
611	19499
612	18530
613	17768
614	17384
615	16973
616	16220
617	15750
618	15008
619	14200
620	13515
621	13493
622	13396
623	13281
624	12510
625	12284
626	12169
627	11781
628	11999
629	12373
630	11657
631	11113
632	10968
633	11279
634	10929
635	11454
636	11477
637	11358
638	10638
639	10266
640	10746
641	10584
642	10190
643	10080
644	10328
645	10673
646	10834
647	10543
648	10439
649	10692
650	10754
651	10569
652	10758
653	10898
654	10863
655	10970
656	10875
657	11260
658	10830
659	10924
660	10792
661	10774
662	10605
663	9825
664	9572
665	9271
666	9502
667	9291
668	8857
669	8641
670	8779
671	9044
672	8725
673	8078
674	7775
675	8180
676	7989
677	7640
678	8127
679	8152
680	7866
681	7493
682	6678
683	6690
684	6862
685	7085
686	6952
687	6955
688	6602
689	6493
690	6924
691	7037
692	6140
693	5729
694	5852
695	6320
696	6397
697	6305
698	5800
699	5497
700	5817
701	6112
702	6075
703	5530
704	5150
705	5519
706	5989
707	5521
708	5352
709	5561
710	5550
711	5447
712	5351
713	5140
714	4923
715	4640
716	4481
717	4488
718	4562
719	4623
720	4860
721	5018
722	4832
723	4803
724	4804
725	4345
726	4331
727	4533
728	4527
729	4364
730	4093
731	4191
732	4252
733	4432
734	4363
735	4284
736	4071
737	3771
738	4099
739	4165
740	4287
741	4119
742	4048
743	4272
744	4079
745	4113
746	4069
747	4150
748	3930
749	3635
750	3438
751	3356
752	3053
753	2986
754	3090
755	3035
756	3025
757	3003
758	2738
759	2917
760	2889
761	2919
762	2868
763	2781
764	2705
765	3074
766	3210
767	2916
768	2989
769	2900
770	2607
771	2585
772	2747
773	2653
774	2638
775	2666
776	3050
777	2881
778	2663
779	2491
780	2580
781	2596
782	2510
783	2543
784	2313
785	2438
786	2347
787	2268
788	1983
789	1758
790	1917
791	1927
792	1874
793	1907
794	2217
795	2316
796	2139
797	2052
798	1868
799	1673
800	1736
801	1854
802	2034
803	2099
804	2169
805	2035
806	1889
807	2135
808	2071
809	2053
810	2040
811	1659
812	1711
813	1566
814	1486
815	2068
816	2356
817	2061
818	1828
819	1967
820	1962
821	2033
822	1897
823	1625
824	1614
825	1793
826	2166
827	2326
828	2362
829	2146
830	1850
831	1633
832	1580
833	1595
834	1802
835	2025
836	2121
837	1900
838	1876
839	1919
840	1723
841	1788
842	1652
843	1635
844	1655
845	1555
846	1641
847	1863
848	1577
849	1559
850	1471
851	1483
852	1704
853	1743
854	1764
855	1925
856	1802
857	1563
858	1735
859	1526
860	1628
861	1967
862	1969
863	1743
864	1790
865	1962
866	1822
867	1522
868	1384
869	1805
870	1735
871	1786
872	1852
873	1762
874	1782
875	1827
876	2042
877	1994
878	1695
879	1738
880	1523
881	1396
882	1564
883	1406
884	1409
885	1166
886	1500
887	1684
888	1658
889	1404
890	1540
891	1795
892	1696
893	1657
894	1568
895	1689
896	1803
897	1824
898	1868
899	1743
900	1806
901	1875
902	1520
903	1633
904	1827
905	1722
906	1489
907	1424
908	1425
909	1644
910	1847
911	1910
912	1833
913	1840
914	1754
915	1384
916	1388
917	1558
918	1722
919	1789
920	1623
921	1586
922	1660
923	1485
924	1555
925	1380
926	1507
927	1409
928	1375
929	1466
930	1348
931	1701
932	1546
933	1196
934	1260
935	1371
936	1357
937	1323
938	1583
939	1819
940	1607
941	1495
942	1512
943	1286
944	1414
945	1610
946	1516
947	1616
948	1574
949	1543
950	1411
951	1666
952	1653
953	1598
954	1758
955	1830
956	1404
957	1403
958	1621
959	1962
960	1934
961	2171
962	1526
963	1403
964	1715
965	1725
966	1728
967	1635
968	1336
969	1243
970	1407
971	1484
972	1574
973	1585
974	1424
975	1767
976	1739
977	1723
978	1465
979	1473
980	1512
981	1553
982	1686
983	1609
984	1369
985	1570
986	1444
987	1835
988	1608
989	1492
990	1298
991	1328
992	1491
993	1418
994	1285
995	1543
996	1744
997	1669
998	1423
999	1387
1000	1282
1001	1301
1002	1510
1003	1434
1004	1466
1005	1376
1006	1180
1007	1129
1008	1311
1009	1466
1010	1295
1011	1260
1012	1505
1013	1414
1014	1509
1015	1263
1016	1186
1017	1293
1018	1668
1019	1455
1020	1545
1021	1221
1022	1203
1023	1232
1024	1236