1	923
2	1086
3	1133
4	1235
5	1270
6	1210
7	1186
8	958
9	1039
10	1266
11	1351
12	1266
13	939
14	766
15	871
16	846
17	1017
18	1132
19	1469
20	1673
21	1597
22	1312
23	1036
24	968
25	1446
26	1739
27	1839
28	1741
29	1503
30	1685
31	2092
32	2286
33	2190
34	1991
35	1789
36	1994
37	2103
38	2061
39	2250
40	2032
41	1739
42	1850
43	1817
44	1946
45	2141
46	1890
47	1907
48	1924
49	2472
50	2992
51	3693
52	4044
53	3452
54	2528
55	1723
56	1356
57	1045
58	1013
59	1187
60	1542
61	1722
62	1809
63	1853
64	1698
65	1907
66	2164
67	2479
68	2499
69	2691
70	2571
71	2173
72	1934
73	2332
74	2929
75	3567
76	3689
77	3291
78	2670
79	2600
80	2653
81	2783
82	2326
83	1689
84	1079
85	788
86	840
87	966
88	1301
89	1437
90	2050
91	2417
92	2833
93	2637
94	2950
95	2646
96	2615
97	2213
98	1912
99	1794
100	1945
101	1918
102	2024
103	2610
104	2830
105	2444
106	1836
107	1423
108	1739
109	2181
110	2530
111	2764
112	2768
113	2608
114	2421
115	2441
116	3026
117	3555
118	3832
119	3657
120	3089
121	2671
122	2119
123	1704
124	1573
125	2024
126	2681
127	3156
128	3093
129	3231
130	3470
131	3549
132	3221
133	2652
134	2234
135	2157
136	2632
137	2999
138	3482
139	3290
140	2761
141	2317
142	2221
143	2423
144	2539
145	2437
146	2473
147	2128
148	1933
149	2006
150	2346
151	2858
152	3510
153	3411
154	3033
155	2717
156	3237
157	4319
158	5246
159	5280
160	4580
161	4010
162	4077
163	4439
164	4529
165	4229
166	4143
167	4416
168	5417
169	6179
170	6332
171	5500
172	4312
173	4243
174	4570
175	4970
176	5481
177	5768
178	5457
179	5015
180	4832
181	4939
182	4662
183	4942
184	4996
185	5376
186	5806
187	6721
188	7020
189	7541
190	8228
191	8961
192	9029
193	8996
194	8966
195	9702
196	10794
197	11399
198	10302
199	8725
200	7798
201	7845
202	7543
203	7435
204	7606
205	8005
206	9074
207	10371
208	11342
209	11747
210	11192
211	10664
212	10161
213	9780
214	9689
215	10247
216	10348
217	9779
218	8394
219	7420
220	6354
221	5836
222	5963
223	6875
224	7643
225	7845
226	7328
227	6125
228	5482
229	5062
230	5406
231	5602
232	5758
233	5707
234	5636
235	5876
236	6077
237	5815
238	4546
239	4011
240	3872
241	4676
242	4654
243	3913
244	3011
245	2703
246	3400
247	4336
248	4677
249	4780
250	5153
251	6480
252	7227
253	6762
254	5356
255	4618
256	4634
257	5068
258	5271
259	5072
260	4287
261	4210
262	5028
263	5896
264	5720
265	5070
266	5224
267	5942
268	6226
269	5390
270	4680
271	4210
272	3866
273	3670
274	3598
275	3808
276	3902
277	3695
278	3523
279	3391
280	3865
281	3960
282	4040
283	4347
284	4799
285	5425
286	5855
287	5797
288	5581
289	5404
290	5544
291	5157
292	4264
293	3861
294	3668
295	3553
296	3259
297	3247
298	3559
299	3799
300	3802
301	3740
302	3561
303	3573
304	3970
305	4910
306	5342
307	5144
308	4844
309	4331
310	4029
311	4256
312	4133
313	4039
314	3893
315	3321
316	3072
317	4039
318	5053
319	4959
320	4307
321	4238
322	4148
323	4301
324	4542
325	4373
326	4026
327	3675
328	3770
329	4411
330	5237
331	6245
332	6499
333	5785
334	5407
335	5736
336	5320
337	4925
338	4730
339	4595
340	4353
341	3961
342	4213
343	4202
344	4049
345	4830
346	6131
347	6442
348	5563
349	5460
350	6076
351	6388
352	5937
353	5373
354	5207
355	5835
356	6200
357	6113
358	6475
359	6867
360	6393
361	4977
362	3897
363	4178
364	6071
365	8187
366	8001
367	6104
368	4660
369	4846
370	5319
371	5268
372	4948
373	5007
374	5790
375	6855
376	7659
377	8224
378	8106
379	8284
380	8522
381	7983
382	6627
383	5278
384	5439
385	6298
386	7233
387	7768
388	8911
389	10248
390	10448
391	10720
392	11144
393	11254
394	11028
395	10446
396	10386
397	10409
398	10225
399	10026
400	9643
401	9544
402	9929
403	10424
404	10735
405	11454
406	12430
407	12601
408	12421
409	11881
410	11298
411	10619
412	10819
413	11807
414	13003
415	12833
416	12580
417	12451
418	13203
419	14789
420	17536
421	17571
422	16057
423	14935
424	15671
425	15538
426	13734
427	11607
428	11696
429	12367
430	13489
431	13413
432	12514
433	11959
434	11617
435	11318
436	10491
437	9277
438	8513
439	9054
440	10506
441	10596
442	9722
443	7922
444	6973
445	7589
446	8812
447	10089
448	12404
449	13327
450	11701
451	10564
452	10850
453	11173
454	10349
455	9981
456	10001
457	9505
458	9213
459	10633
460	11857
461	11931
462	11165
463	13011
464	17133
465	18611
466	16953
467	15352
468	13186
469	12581
470	12152
471	13686
472	15906
473	16927
474	16506
475	15943
476	16636
477	17470
478	17948
479	18858
480	19982
481	22340
482	22625
483	21032
484	20212
485	19610
486	20357
487	21787
488	22545
489	22180
490	21131
491	20425
492	20940
493	22341
494	22015
495	20511
496	17446
497	16382
498	18032
499	17683
500	15771
501	15370
502	15882
503	14329
504	12280
505	11521
506	13172
507	15473
508	15899
509	15167
510	13235
511	10493
512	8402
513	8246
514	8100
515	8343
516	8803
517	8103
518	6935
519	5993
520	5239
521	5705
522	7019
523	7963
524	8188
525	7008
526	6176
527	6649
528	7226
529	7453
530	7799
531	6485
532	5786
533	6430
534	6514
535	7057
536	8290
537	7173
538	5577
539	5027
540	6239
541	7121
542	6438
543	4912
544	4053
545	5010
546	6030
547	5259
548	4527
549	5417
550	6264
551	5667
552	4622
553	4739
554	5069
555	5126
556	5694
557	7029
558	8196
559	7729
560	6379
561	6177
562	6062
563	5291
564	4598
565	4618
566	4914
567	5300
568	6033
569	6107
570	5296
571	3974
572	3690
573	4309
574	4248
575	3621
576	3007
577	2732
578	3182
579	3645
580	3597
581	3084
582	2511
583	2001
584	2426
585	3984
586	4848
587	4534
588	4458
589	4095
590	3622
591	3202
592	2820
593	2426
594	3000
595	3320
596	2982
597	2766
598	3334
599	4116
600	4466
601	3478
602	2621
603	2984
604	4754
605	6129
606	5260
607	4541
608	3508
609	2297
610	1992
611	2172
612	1978
613	2256
614	3246
615	4428
616	4670
617	3868
618	2163
619	1382
620	1760
621	2220
622	2490
623	2830
624	3417
625	3013
626	2618
627	2445
628	2422
629	2838
630	3226
631	4940
632	5852
633	4872
634	2985
635	2952
636	3743
637	3855
638	3815
639	4069
640	3742
641	3695
642	2849
643	3001
644	3755
645	3253
646	2269
647	1824
648	2383
649	3419
650	3687
651	2966
652	2483
653	1692
654	1464
655	1961
656	2505
657	3309
658	4213
659	3400
660	2177
661	1885
662	2717
663	2691
664	2075
665	1784
666	1987
667	2175
668	2340
669	1973
670	2086
671	2901
672	2958
673	3145
674	3865
675	3977
676	3508
677	2395
678	2032
679	2527
680	3064
681	3328
682	3194
683	2181
684	1827
685	2613
686	2851
687	2989
688	3045
689	3286
690	2843
691	2814
692	2652
693	2278
694	2480
695	2625
696	2754
697	3197
698	3271
699	1921
700	1827
701	2237
702	2450
703	2597
704	2366
705	2637
706	3550
707	3575
708	4067
709	3589
710	1887
711	1749
712	2001
713	1813
714	2543
715	3049
716	2905
717	3788
718	3655
719	2581
720	2454
721	2805
722	3912
723	6023
724	6744
725	5696
726	3510
727	1792
728	1595
729	1892
730	2049
731	1538
732	1317
733	1685
734	1270
735	1056
736	1681
737	3397
738	4082
739	4212
740	3680
741	2593
742	3007
743	4000
744	3607
745	4178
746	5258
747	4965
748	5004
749	6271
750	5260
751	4444
752	4543
753	4055
754	4641
755	5253
756	4887
757	4701
758	4611
759	4095
760	4018
761	5595
762	7875
763	9059
764	7406
765	6739
766	5406
767	4990
768	6641
769	6648
770	4980
771	5511
772	6921
773	7862
774	7640
775	7685
776	9013
777	8139
778	6451
779	5223
780	7275
781	9334
782	10301
783	9282
784	8416
785	8095
786	9206
787	11932
788	9058
789	6773
790	7068
791	8136
792	9511
793	10653
794	10720
795	10717
796	10235
797	8974
798	8278
799	9188
800	8571
801	6957
802	8517
803	11358
804	10672
805	8957
806	8890
807	8840
808	9485
809	11251
810	8471
811	6376
812	7741
813	7844
814	6814
815	7425
816	6528
817	5368
818	6025
819	6578
820	5921
821	6341
822	6011
823	6433
824	7251
825	5669
826	5301
827	6728
828	6463
829	7331
830	7803
831	7379
832	5942
833	6293
834	5444
835	5823
836	7167
837	6740
838	6708
839	5753
840	5310
841	4234
842	4496
843	3946
844	3541
845	4656
846	4721
847	6123
848	5645
849	2997
850	1822
851	1790
852	1686
853	1668
854	1898
855	2340
856	3606
857	3591
858	2744
859	1905
860	1259
861	1334
862	1458
863	1383
864	1831
865	1814
866	2107
867	3309
868	2359
869	1071
870	454
871	536
872	866
873	1219
874	1172
875	1408
876	1800
877	1849
878	1585
879	1544
880	2446
881	2480
882	1901
883	1388
884	1695
885	1606
886	340
887	-67
888	820
889	742
890	1047
891	1928
892	2383
893	2060
894	1459
895	1435
896	1777
897	983
898	674
899	621
900	1100
901	1505
902	2090
903	2741
904	1955
905	1840
906	1177
907	1712
908	2817
909	2232
910	1455
911	2555
912	2570
913	1577
914	1422
915	1620
916	1434
917	760
918	1020
919	1309
920	1418
921	908
922	635
923	833
924	1490
925	1888
926	1842
927	1332
928	1223
929	1494
930	1148
931	1077
932	2221
933	1948
934	1030
935	1373
936	2261
937	2483
938	1801
939	801
940	753
941	891
942	870
943	454
944	649
945	1449
946	2545
947	2674
948	2215
949	1721
950	751
951	575
952	1056
953	1184
954	672
955	244
956	119
957	92
958	192
959	242
960	289
961	897
962	978
963	1005
964	468
965	46
966	181
967	170
968	277
969	294
970	306
971	198
972	135
973	593
974	761
975	658
976	919
977	625
978	426
979	354
980	1056
981	1600
982	915
983	303
984	377
985	708
986	952
987	1184
988	566
989	409
990	1278
991	2242
992	1562
993	1440
994	1094
995	973
996	1220
997	1387
998	1484
999	624
1000	321
1001	836
1002	888
1003	268
1004	254
1005	238
1006	469
1007	333
1008	365
1009	474
1010	886
1011	964
1012	1181
1013	1174
1014	808
1015	383
1016	192
1017	208
1018	271
1019	908
1020	1048
1021	718
1022	680
1023	938
1024	2671