1	1569
2	1674
3	1623
4	1580
5	1660
6	1699
7	1779
8	1882
9	1687
10	1794
11	1749
12	1602
13	1612
14	1667
15	1789
16	1661
17	1583
18	1648
19	1588
20	1647
21	1867
22	1839
23	1785
24	1676
25	1605
26	1679
27	1605
28	1610
29	1537
30	1484
31	1561
32	1664
33	1756
34	1946
35	1754
36	1677
37	1687
38	1714
39	1649
40	1790
41	1542
42	1869
43	1622
44	1706
45	1832
46	2013
47	1927
48	1930
49	1953
50	1929
51	1904
52	1809
53	1840
54	1867
55	1775
56	1721
57	1764
58	1886
59	1862
60	1924
61	1942
62	2070
63	2030
64	2032
65	1698
66	1704
67	1781
68	1852
69	2032
70	1925
71	2048
72	2130
73	2239
74	2308
75	2202
76	2248
77	2180
78	2144
79	2077
80	2217
81	2113
82	2173
83	2204
84	2296
85	2263
86	2437
87	2466
88	2533
89	2442
90	2659
91	2689
92	2952
93	2824
94	3278
95	3125
96	3527
97	3416
98	3384
99	3428
100	3381
101	3441
102	3486
103	3701
104	3899
105	4108
106	4398
107	4450
108	4459
109	4651
110	4940
111	5281
112	5365
113	5431
114	5383
115	5515
116	5835
117	6160
118	6354
119	6527
120	6474
121	7066
122	6889
123	7285
124	7249
125	7303
126	7220
127	7364
128	7223
129	7231
130	6963
131	6910
132	6763
133	6689
134	6624
135	6520
136	6005
137	6038
138	5570
139	5319
140	5534
141	5279
142	5152
143	4971
144	4745
145	4379
146	4207
147	3999
148	4058
149	4184
150	4083
151	3893
152	3896
153	3658
154	3562
155	3561
156	3609
157	3360
158	3299
159	2997
160	2973
161	2864
162	2878
163	2926
164	3064
165	3129
166	3150
167	2988
168	2850
169	2929
170	2937
171	3054
172	3045
173	2912
174	2604
175	2514
176	2343
177	2263
178	2202
179	2317
180	2297
181	2428
182	2240
183	2381
184	2315
185	2099
186	2028
187	2104
188	2115
189	2187
190	2133
191	2149
192	1972
193	2002
194	1866
195	2066
196	1975
197	2033
198	1938
199	1949
200	1971
201	1905
202	1907
203	1980
204	1802
205	1977
206	1908
207	1825
208	1828
209	1709
210	1913
211	2020
212	2055
213	2045
214	1941
215	1914
216	1943
217	1922
218	1756
219	1794
220	1840
221	1802
222	1941
223	1766
224	1795
225	1772
226	1890
227	1723
228	1834
229	1740
230	1816
231	1939
232	2104
233	1997
234	1937
235	2011
236	1925
237	2097
238	2032
239	2086
240	2125
241	1886
242	1967
243	1925
244	1989
245	1937
246	2102
247	2197
248	2238
249	2200
250	1980
251	1965
252	2063
253	2311
254	2365
255	2433
256	2434
257	2118
258	2200
259	2242
260	2186
261	2311
262	2178
263	2133
264	1990
265	1932
266	2109
267	2156
268	2401
269	2383
270	2319
271	2385
272	2323
273	2062
274	2073
275	1958
276	2003
277	2153
278	2210
279	2196
280	2127
281	2236
282	2415
283	2317
284	2348
285	2573
286	2505
287	2580
288	2589
289	2289
290	2537
291	2513
292	2621
293	2511
294	2533
295	2653
296	2544
297	2578
298	2502
299	2359
300	2353
301	2440
302	2435
303	2431
304	2337
305	2553
306	2531
307	2741
308	2988
309	3239
310	3281
311	3067
312	2961
313	3228
314	3234
315	3223
316	3081
317	3059
318	3310
319	3388
320	3625
321	3493
322	3739
323	3973
324	3964
325	3990
326	3973
327	3929
328	4027
329	3942
330	3923
331	4022
332	4206
333	4412
334	4327
335	4206
336	4250
337	4191
338	4225
339	4385
340	4434
341	4633
342	4595
343	4641
344	4414
345	4137
346	4019
347	4054
348	4311
349	4303
350	4228
351	4069
352	4220
353	4282
354	4081
355	4160
356	4063
357	4116
358	4124
359	3925
360	3890
361	4290
362	4350
363	4381
364	4327
365	4313
366	4096
367	4078
368	4091
369	4420
370	4129
371	4140
372	4031
373	4188
374	4058
375	3818
376	3968
377	4027
378	3987
379	3877
380	4009
381	4014
382	3844
383	3558
384	3480
385	3635
386	3454
387	3468
388	3547
389	3690
390	3819
391	4106
392	3985
393	4027
394	3919
395	3550
396	3915
397	4127
398	4396
399	4350
400	4141
401	4122
402	3979
403	4303
404	4488
405	4590
406	4507
407	4697
408	4781
409	5115
410	5345
411	5143
412	5052
413	5037
414	5259
415	5095
416	5150
417	4931
418	4889
419	5148
420	5394
421	5549
422	5860
423	6089
424	6277
425	6015
426	6053
427	5709
428	5589
429	5636
430	5964
431	6361
432	6354
433	6341
434	6173
435	6083
436	6072
437	5965
438	5977
439	6108
440	6224
441	6008
442	6214
443	6279
444	6472
445	6436
446	6467
447	6422
448	6667
449	6568
450	6850
451	6850
452	6926
453	6972
454	7104
455	7152
456	7024
457	7013
458	7265
459	7270
460	7532
461	7925
462	7852
463	7846
464	8390
465	8462
466	8857
467	9235
468	9627
469	10106
470	10068
471	10489
472	10733
473	11468
474	11919
475	12304
476	12801
477	12878
478	12699
479	12682
480	12501
481	12698
482	12818
483	13361
484	14002
485	14038
486	14159
487	14761
488	15243
489	15357
490	15519
491	15719
492	15172
493	15654
494	16004
495	16758
496	17132
497	16767
498	16432
499	16126
500	16256
501	16428
502	16482
503	16763
504	16658
505	17040
506	17652
507	18599
508	19600
509	20862
510	21497
511	20961
512	20644
513	20905
514	21118
515	21582
516	21951
517	22932
518	23477
519	23424
520	23597
521	23477
522	24309
523	25182
524	26190
525	26531
526	26962
527	27841
528	28348
529	28550
530	28963
531	30637
532	31448
533	31461
534	31266
535	32194
536	33239
537	33462
538	34000
539	34480
540	34947
541	36084
542	36393
543	36264
544	35577
545	37224
546	38292
547	38439
548	37845
549	37961
550	38205
551	38246
552	37390
553	36425
554	34754
555	33602
556	32900
557	34378
558	34819
559	35311
560	35136
561	34641
562	34558
563	34572
564	35166
565	34812
566	34904
567	35104
568	35727
569	35561
570	35693
571	35500
572	35767
573	35926
574	36332
575	37358
576	36898
577	36768
578	37502
579	38236
580	38688
581	38556
582	38445
583	37937
584	36967
585	36686
586	36718
587	37561
588	38131
589	37131
590	35120
591	34154
592	34067
593	33618
594	32411
595	31258
596	31246
597	31039
598	30521
599	29362
600	27639
601	26706
602	26182
603	24944
604	23478
605	22915
606	22007
607	20653
608	19318
609	18612
610	18447
611	18040
612	17669
613	17698
614	17868
615	17623
616	16330
617	15677
618	15758
619	15268
620	14597
621	13924
622	13887
623	13924
624	13257
625	12762
626	12145
627	11820
628	11708
629	11131
630	10928
631	11232
632	11208
633	11470
634	11330
635	11542
636	11462
637	11406
638	10870
639	10380
640	10640
641	10403
642	10502
643	10803
644	11373
645	11718
646	12032
647	11993
648	12015
649	11845
650	11709
651	11269
652	10769
653	10502
654	10966
655	10774
656	10347
657	9958
658	9699
659	9793
660	9570
661	9571
662	9940
663	9411
664	9784
665	10206
666	10268
667	9458
668	8926
669	9279
670	9154
671	9146
672	8952
673	8619
674	8379
675	7800
676	7546
677	7670
678	7549
679	7559
680	6970
681	6854
682	7182
683	7258
684	6983
685	7011
686	6808
687	6847
688	6914
689	6917
690	6637
691	6417
692	6079
693	6360
694	6366
695	6172
696	5773
697	5835
698	5756
699	5744
700	5524
701	5543
702	5782
703	5658
704	5132
705	5303
706	5105
707	4735
708	4869
709	5269
710	5298
711	5222
712	4979
713	4344
714	4376
715	4699
716	4858
717	4557
718	4217
719	4300
720	4558
721	4543
722	4565
723	4731
724	4647
725	4364
726	4291
727	4473
728	4305
729	4288
730	4391
731	4396
732	4469
733	4303
734	4142
735	3972
736	3942
737	3800
738	3904
739	3917
740	4331
741	4279
742	4095
743	3925
744	3655
745	3462
746	3392
747	3527
748	3752
749	3543
750	3234
751	3335
752	3349
753	3208
754	2993
755	3085
756	2904
757	2917
758	2723
759	2587
760	2534
761	2888
762	2625
763	2477
764	2692
765	2777
766	2776
767	2735
768	2898
769	2580
770	2655
771	2730
772	2707
773	2560
774	2421
775	2359
776	2507
777	2236
778	2255
779	2147
780	2212
781	2239
782	2260
783	2074
784	2085
785	2119
786	2096
787	2412
788	2387
789	2178
790	2219
791	2020
792	2034
793	2118
794	2284
795	2359
796	2254
797	2253
798	2108
799	2124
800	1935
801	2091
802	2323
803	2275
804	1940
805	2038
806	2162
807	2297
808	2301
809	2017
810	1951
811	1709
812	1830
813	1944
814	2021
815	1828
816	1916
817	1804
818	1798
819	2041
820	1698
821	1596
822	1783
823	1890
824	1817
825	2012
826	1903
827	1717
828	1610
829	1614
830	1767
831	1822
832	1635
833	1790
834	1769
835	1686
836	1662
837	1720
838	2027
839	2135
840	2010
841	1765
842	1677
843	1665
844	1941
845	2009
846	2064
847	1892
848	1836
849	1879
850	1902
851	2040
852	2016
853	1889
854	1672
855	1710
856	1717
857	1670
858	1672
859	1490
860	1753
861	1765
862	1619
863	1584
864	1536
865	1766
866	1974
867	1762
868	1401
869	1703
870	1699
871	1339
872	1528
873	1958
874	2114
875	2055
876	2046
877	1777
878	1485
879	1511
880	1682
881	1602
882	1502
883	1328
884	1621
885	1601
886	1694
887	1600
888	1535
889	1387
890	1546
891	1813
892	1700
893	1489
894	1410
895	1462
896	1681
897	1704
898	1557
899	1686
900	1659
901	1612
902	1539
903	1684
904	1921
905	2035
906	1867
907	1839
908	1946
909	1812
910	1634
911	1659
912	1298
913	1343
914	1574
915	1698
916	1658
917	1536
918	1553
919	1561
920	1655
921	1514
922	1619
923	1630
924	1490
925	1515
926	1472
927	1410
928	1527
929	1442
930	1642
931	1589
932	1436
933	1519
934	1457
935	1420
936	1400
937	1486
938	1680
939	1499
940	1503
941	1737
942	1652
943	1470
944	1445
945	1404
946	1450
947	1678
948	1656
949	1689
950	1485
951	1686
952	1710
953	1660
954	1380
955	1442
956	1615
957	1566
958	1502
959	1432
960	1391
961	1371
962	1396
963	1432
964	1476
965	1496
966	1275
967	1053
968	985
969	1280
970	1225
971	1377
972	1410
973	1643
974	1798
975	1544
976	1308
977	1523
978	1578
979	1549
980	1340
981	1367
982	1529
983	1564
984	1403
985	1429
986	1244
987	1446
988	1623
989	1353
990	1390
991	1665
992	1406
993	1572
994	1499
995	1731
996	1648
997	1695
998	1600
999	1454
1000	1579
1001	1324
1002	1434
1003	1620
1004	1432
1005	1170
1006	1265
1007	1290
1008	1494
1009	1393
1010	1343
1011	1432
1012	1481
1013	1391
1014	1449
1015	1581
1016	1688
1017	1553
1018	1722
1019	1713
1020	1696
1021	1619
1022	1613
1023	1545
1024	1792