1	1086
2	1295
3	1344
4	1368
5	1055
6	902
7	803
8	980
9	1138
10	1297
11	1582
12	1733
13	1878
14	1817
15	1640
16	1417
17	1327
18	984
19	853
20	776
21	564
22	650
23	614
24	589
25	882
26	1103
27	1288
28	1218
29	1059
30	963
31	896
32	950
33	1261
34	1696
35	1718
36	1535
37	1219
38	952
39	847
40	910
41	1155
42	1521
43	1810
44	1911
45	2151
46	1716
47	1445
48	1375
49	1233
50	1335
51	1329
52	1092
53	965
54	839
55	614
56	841
57	850
58	1393
59	1835
60	1936
61	1719
62	1581
63	1566
64	1743
65	1787
66	1603
67	1314
68	970
69	588
70	407
71	672
72	1127
73	1921
74	2250
75	2347
76	2050
77	1740
78	1371
79	1189
80	1191
81	1326
82	1648
83	1946
84	2211
85	2324
86	1948
87	1626
88	1651
89	1775
90	1780
91	1951
92	2008
93	1828
94	1508
95	1284
96	1409
97	1842
98	2266
99	2240
100	1569
101	998
102	647
103	651
104	811
105	963
106	984
107	1280
108	1584
109	2051
110	2604
111	2850
112	2512
113	1708
114	1062
115	1019
116	1272
117	1499
118	1454
119	1152
120	907
121	800
122	740
123	1088
124	1629
125	1973
126	2460
127	2658
128	2706
129	2514
130	2382
131	2115
132	2205
133	2189
134	1991
135	1834
136	1783
137	1561
138	1495
139	1339
140	1470
141	1353
142	1129
143	951
144	630
145	790
146	1062
147	1656
148	1834
149	1615
150	1404
151	1084
152	1291
153	1242
154	1382
155	1239
156	1087
157	943
158	1173
159	1506
160	1652
161	1643
162	1430
163	1182
164	1071
165	814
166	735
167	589
168	768
169	701
170	778
171	726
172	753
173	770
174	1345
175	1796
176	2066
177	1787
178	1601
179	1316
180	1274
181	1367
182	1639
183	2073
184	2588
185	2927
186	2629
187	2193
188	1526
189	1340
190	1405
191	1299
192	1303
193	1101
194	947
195	622
196	457
197	628
198	702
199	773
200	928
201	976
202	851
203	604
204	726
205	1069
206	1107
207	1092
208	1073
209	1168
210	1240
211	1114
212	981
213	1010
214	1278
215	2013
216	2394
217	2618
218	2217
219	1898
220	1567
221	1523
222	1521
223	1426
224	1223
225	1373
226	1816
227	2396
228	2517
229	2602
230	2326
231	2252
232	2466
233	2919
234	3572
235	3771
236	3297
237	2664
238	2266
239	2096
240	1871
241	1525
242	1345
243	1484
244	1578
245	1700
246	1846
247	1620
248	1759
249	2473
250	2915
251	2929
252	2477
253	2060
254	1790
255	1798
256	1426
257	1494
258	1438
259	1348
260	1289
261	1592
262	2138
263	2252
264	1930
265	1588
266	1653
267	1837
268	1771
269	1327
270	1036
271	1130
272	1061
273	923
274	774
275	681
276	1244
277	1245
278	1230
279	859
280	878
281	1100
282	1153
283	1005
284	861
285	1074
286	1608
287	3150
288	5679
289	9483
290	12743
291	15351
292	16106
293	16700
294	17878
295	19539
296	20455
297	21532
298	20894
299	18981
300	17541
301	16137
302	13290
303	9957
304	7654
305	7121
306	7803
307	8797
308	9973
309	10726
310	10981
311	10836
312	10759
313	10497
314	10012
315	9162
316	8492
317	8175
318	8167
319	8357
320	8221
321	7875
322	7756
323	7239
324	6180
325	5776
326	6267
327	6939
328	7838
329	8277
330	8533
331	8039
332	8052
333	8138
334	7967
335	7757
336	7948
337	7699
338	7677
339	7754
340	8040
341	7407
342	6682
343	6974
344	8809
345	10391
346	11024
347	10329
348	8831
349	7371
350	6318
351	5848
352	5436
353	5137
354	5827
355	7454
356	8953
357	9675
358	9887
359	10055
360	9386
361	7398
362	5976
363	5558
364	5821
365	6647
366	7737
367	7689
368	6654
369	6455
370	6470
371	6642
372	6493
373	6525
374	7496
375	8030
376	7654
377	7754
378	8101
379	8483
380	8051
381	6588
382	5758
383	5428
384	5278
385	5835
386	5854
387	5948
388	6467
389	7190
390	7085
391	6231
392	4939
393	4760
394	5209
395	6214
396	7873
397	10621
398	12174
399	11029
400	8703
401	7042
402	5928
403	5026
404	4817
405	5983
406	7959
407	8711
408	7512
409	5525
410	4292
411	3191
412	2816
413	3279
414	4088
415	4677
416	5798
417	6754
418	7160
419	6983
420	5907
421	4144
422	3131
423	2751
424	3345
425	4619
426	6304
427	7775
428	8295
429	8166
430	7615
431	6925
432	5964
433	4890
434	4156
435	4245
436	5375
437	6836
438	7706
439	7185
440	6456
441	6670
442	7164
443	6702
444	5910
445	5770
446	6498
447	5997
448	5046
449	4630
450	4900
451	4945
452	4759
453	4112
454	3571
455	3903
456	4429
457	4561
458	4966
459	5239
460	5377
461	5945
462	6399
463	6921
464	7271
465	8204
466	8680
467	7845
468	5778
469	4411
470	3626
471	3658
472	3388
473	3775
474	3592
475	3716
476	4403
477	5367
478	6563
479	6542
480	5146
481	4197
482	3697
483	2884
484	3041
485	4315
486	5546
487	6216
488	6715
489	6595
490	6428
491	6072
492	5251
493	4459
494	3357
495	2702
496	2918
497	2918
498	2779
499	2834
500	3519
501	4432
502	4314
503	4535
504	5587
505	5855
506	4047
507	2868
508	2849
509	2566
510	1945
511	1687
512	1856
513	2077
514	2571
515	3815
516	4834
517	5118
518	4858
519	5219
520	5587
521	5105
522	4266
523	4217
524	4949
525	4715
526	3887
527	3357
528	2776
529	2736
530	3893
531	5281
532	5120
533	4695
534	3924
535	3894
536	4499
537	5338
538	5435
539	4819
540	4587
541	4064
542	3128
543	2672
544	2447
545	1796
546	2174
547	3336
548	4489
549	6536
550	7303
551	5531
552	3626
553	2644
554	1806
555	1591
556	2209
557	3121
558	3574
559	4196
560	5607
561	6055
562	4945
563	4745
564	6027
565	6268
566	4478
567	3646
568	3869
569	3494
570	3534
571	3925
572	4230
573	4009
574	3481
575	3907
576	4820
577	5084
578	4970
579	6035
580	7029
581	6305
582	4814
583	3394
584	2724
585	2933
586	2933
587	2545
588	2261
589	2896
590	4631
591	5862
592	6198
593	6795
594	8325
595	7876
596	6512
597	5747
598	5569
599	5091
600	4094
601	3841
602	3711
603	3201
604	2666
605	3378
606	4688
607	5442
608	6456
609	6887
610	6698
611	5928
612	6028
613	7137
614	7302
615	7259
616	7365
617	6839
618	6213
619	5869
620	5867
621	6838
622	6888
623	5608
624	5356
625	7240
626	9430
627	9837
628	8731
629	7459
630	6891
631	6747
632	6927
633	7036
634	5772
635	5007
636	6302
637	7604
638	6975
639	6402
640	6248
641	6781
642	9026
643	10355
644	9011
645	6858
646	5430
647	4541
648	5124
649	4882
650	4751
651	4813
652	5294
653	5293
654	5658
655	6718
656	7471
657	6990
658	6511
659	6241
660	6513
661	7284
662	8158
663	9820
664	10303
665	8886
666	6315
667	4484
668	3393
669	3299
670	3391
671	3873
672	4388
673	4759
674	5973
675	8295
676	9659
677	8568
678	8095
679	10243
680	12408
681	12389
682	10687
683	8051
684	7369
685	8508
686	9198
687	9806
688	9872
689	9008
690	7513
691	6545
692	7285
693	10371
694	11283
695	9083
696	8080
697	8132
698	6998
699	6300
700	8685
701	11118
702	11380
703	10621
704	8235
705	7237
706	7308
707	8055
708	8659
709	8216
710	6144
711	5509
712	7034
713	9132
714	11492
715	13455
716	12510
717	11200
718	11601
719	11280
720	9102
721	8596
722	7210
723	7358
724	7671
725	6599
726	7164
727	8182
728	8069
729	7069
730	6384
731	5500
732	5097
733	5446
734	7041
735	7480
736	7638
737	9365
738	8626
739	6471
740	5478
741	6103
742	6412
743	5115
744	3546
745	2732
746	2732
747	3794
748	4215
749	4057
750	3279
751	4148
752	5424
753	5942
754	5455
755	5436
756	6332
757	7672
758	7582
759	7830
760	8892
761	8373
762	5284
763	4507
764	4864
765	4311
766	4144
767	3759
768	3161
769	2374
770	2872
771	3819
772	4518
773	5782
774	6553
775	5760
776	6578
777	7998
778	7619
779	6105
780	5687
781	3755
782	2225
783	2479
784	4441
785	5363
786	4916
787	4146
788	3601
789	3050
790	2504
791	2871
792	3672
793	5404
794	6171
795	5028
796	3746
797	3998
798	4243
799	4564
800	4623
801	3707
802	2994
803	3243
804	3712
805	4304
806	3818
807	3617
808	3186
809	3119
810	3790
811	5035
812	5055
813	3243
814	4179
815	6447
816	6651
817	7132
818	6559
819	5522
820	6404
821	6856
822	4469
823	4312
824	6096
825	5853
826	4995
827	4181
828	3724
829	3787
830	2382
831	1533
832	1414
833	1194
834	1746
835	2499
836	3073
837	3639
838	4822
839	4602
840	4348
841	4711
842	5187
843	3887
844	3124
845	2882
846	2978
847	2246
848	1930
849	2263
850	2667
851	2697
852	2404
853	2052
854	1731
855	1958
856	3322
857	5409
858	6540
859	6761
860	3827
861	2845
862	3069
863	2810
864	3956
865	5020
866	4803
867	3089
868	1499
869	1818
870	2412
871	2490
872	3147
873	2662
874	1734
875	2027
876	3445
877	3995
878	3147
879	2093
880	1686
881	2575
882	2750
883	2674
884	2718
885	3678
886	3761
887	3819
888	3589
889	3120
890	2563
891	1781
892	1152
893	718
894	748
895	1038
896	1656
897	1123
898	1073
899	1133
900	1203
901	1535
902	1685
903	2035
904	2996
905	4607
906	6406
907	5983
908	4472
909	3334
910	3616
911	2732
912	1318
913	1722
914	3009
915	3381
916	3494
917	3634
918	2332
919	1723
920	2203
921	2498
922	2114
923	1621
924	2301
925	5189
926	5912
927	3599
928	4396
929	5582
930	4129
931	2601
932	2705
933	2114
934	1636
935	2158
936	1776
937	2197
938	3546
939	3981
940	2390
941	1641
942	2449
943	2246
944	2731
945	3029
946	2889
947	1636
948	2318
949	2923
950	3502
951	3290
952	4613
953	5419
954	5364
955	4037
956	2166
957	1067
958	798
959	1308
960	2350
961	2796
962	2549
963	2323
964	1600
965	1680
966	1489
967	1341
968	1995
969	2611
970	1913
971	1857
972	2162
973	1870
974	1797
975	1866
976	2301
977	2631
978	2925
979	4423
980	5232
981	2374
982	1392
983	1694
984	1951
985	1781
986	2202
987	2841
988	3067
989	1847
990	1132
991	1363
992	1963
993	1453
994	2078
995	2763
996	3070
997	4226
998	3290
999	1698
1000	3002
1001	4447
1002	3662
1003	2936
1004	3829
1005	2739
1006	2244
1007	1640
1008	2041
1009	2063
1010	2131
1011	1487
1012	1597
1013	969
1014	1134
1015	1020
1016	1229
1017	1821
1018	2577
1019	2881
1020	1652
1021	1960
1022	3869
1023	5307
1024	4233