1	1550
2	2051
3	2735
4	2867
5	2662
6	2253
7	1854
8	1643
9	1765
10	1763
11	1740
12	1951
13	2346
14	2729
15	3245
16	3151
17	2724
18	2048
19	1831
20	1437
21	1102
22	800
23	284
24	-41
25	-28
26	209
27	527
28	1060
29	1444
30	2170
31	2713
32	2951
33	2463
34	1936
35	1513
36	1600
37	1988
38	2768
39	3670
40	4091
41	3657
42	2886
43	2125
44	1910
45	2611
46	3182
47	3410
48	2908
49	2319
50	1498
51	1168
52	1124
53	1099
54	1418
55	1719
56	2283
57	2519
58	2559
59	2762
60	2814
61	2860
62	2957
63	2795
64	2406
65	2244
66	1922
67	1753
68	1406
69	1424
70	1324
71	1020
72	975
73	1086
74	1263
75	1517
76	1580
77	2012
78	2556
79	3513
80	4135
81	4505
82	4503
83	4378
84	3945
85	3504
86	3228
87	3024
88	2710
89	2069
90	1716
91	1822
92	2135
93	2310
94	2194
95	1777
96	1950
97	2030
98	2244
99	2296
100	2289
101	2408
102	2588
103	3127
104	3494
105	3476
106	3312
107	3226
108	3053
109	2662
110	2361
111	2474
112	2308
113	2887
114	3429
115	3931
116	4033
117	3571
118	3284
119	2987
120	2648
121	2745
122	3626
123	4681
124	5005
125	4376
126	3264
127	2574
128	2576
129	2844
130	2925
131	2572
132	2444
133	2419
134	2961
135	3655
136	4766
137	5210
138	5418
139	5013
140	4121
141	3514
142	3076
143	3233
144	3265
145	3225
146	3376
147	3611
148	3759
149	3634
150	3343
151	2924
152	2973
153	3159
154	3659
155	4602
156	5518
157	6056
158	5723
159	4775
160	4282
161	4589
162	5340
163	6337
164	7548
165	7930
166	7163
167	5879
168	4953
169	4302
170	4409
171	4871
172	5943
173	7215
174	8004
175	8321
176	8453
177	8422
178	8320
179	8908
180	9430
181	8931
182	7603
183	7339
184	7308
185	7777
186	8297
187	8220
188	8083
189	8104
190	8648
191	9073
192	9032
193	8874
194	8519
195	9261
196	10198
197	11118
198	11166
199	10657
200	9476
201	9171
202	9414
203	10996
204	12172
205	12541
206	12118
207	12018
208	12616
209	13249
210	13083
211	12343
212	11973
213	12051
214	13105
215	13981
216	13840
217	12764
218	11463
219	10121
220	8352
221	7244
222	6593
223	6705
224	7392
225	8371
226	9133
227	9079
228	8866
229	9200
230	9529
231	8541
232	7382
233	6971
234	7099
235	7628
236	7689
237	7171
238	7335
239	7290
240	6191
241	5266
242	4636
243	4782
244	5415
245	6087
246	6342
247	6086
248	5533
249	5060
250	4344
251	4295
252	4313
253	4570
254	4551
255	4304
256	4274
257	4295
258	4675
259	5571
260	6265
261	6139
262	5415
263	5271
264	6113
265	6852
266	6660
267	5440
268	3776
269	3175
270	3365
271	3767
272	3765
273	3751
274	4278
275	4676
276	5727
277	7121
278	8586
279	9554
280	9285
281	7386
282	5470
283	4466
284	4308
285	4836
286	5191
287	5089
288	4927
289	4514
290	4664
291	4676
292	5834
293	6595
294	6574
295	5830
296	4813
297	4870
298	6041
299	6762
300	5743
301	4685
302	4276
303	4612
304	4919
305	5457
306	5534
307	4937
308	4431
309	3929
310	3892
311	4299
312	4688
313	5927
314	7011
315	8219
316	9052
317	9082
318	8207
319	7489
320	7048
321	6040
322	4572
323	3676
324	3886
325	4742
326	5422
327	6263
328	6902
329	7267
330	6654
331	5313
332	4226
333	4014
334	4770
335	6172
336	6831
337	6270
338	5433
339	5779
340	7018
341	7702
342	7661
343	7221
344	6557
345	6198
346	5965
347	5318
348	5342
349	5820
350	5856
351	5557
352	5658
353	6576
354	7904
355	9240
356	10163
357	9702
358	8211
359	5993
360	5269
361	5798
362	6439
363	6942
364	7252
365	6942
366	6437
367	5918
368	5790
369	6117
370	6236
371	6757
372	7730
373	8576
374	8600
375	7935
376	7572
377	7669
378	7915
379	8657
380	9518
381	9401
382	8835
383	8432
384	9045
385	9519
386	9228
387	8845
388	10517
389	13589
390	14947
391	14208
392	13195
393	13103
394	14335
395	14944
396	15567
397	16239
398	15991
399	13925
400	11959
401	12534
402	14919
403	16721
404	16825
405	17011
406	16910
407	16345
408	16028
409	14922
410	13822
411	13139
412	13388
413	12913
414	13458
415	14469
416	15288
417	14818
418	14564
419	14696
420	14992
421	15457
422	17734
423	20285
424	20427
425	18299
426	16645
427	16028
428	16071
429	16607
430	18903
431	19494
432	18298
433	15290
434	13319
435	13341
436	13646
437	13793
438	13749
439	11892
440	10355
441	10277
442	11539
443	12895
444	14988
445	17218
446	18822
447	17713
448	15513
449	14367
450	15489
451	16850
452	16883
453	16091
454	17040
455	18023
456	16282
457	14958
458	15146
459	16245
460	15511
461	15071
462	15627
463	16152
464	16351
465	16560
466	17545
467	17341
468	15898
469	15342
470	16950
471	19600
472	20273
473	19352
474	19600
475	21862
476	24467
477	25412
478	25234
479	24575
480	25982
481	28592
482	28678
483	27874
484	27941
485	28795
486	28319
487	26132
488	23938
489	23598
490	24932
491	25662
492	24798
493	24995
494	25122
495	25849
496	25471
497	23790
498	22911
499	23850
500	25177
501	22289
502	18098
503	16300
504	16045
505	14761
506	12711
507	11496
508	11498
509	12267
510	13975
511	15264
512	14357
513	12310
514	10605
515	10202
516	9960
517	9093
518	7763
519	7180
520	8628
521	10053
522	10215
523	9583
524	8952
525	9092
526	9030
527	7845
528	6870
529	7931
530	9019
531	8830
532	9837
533	10254
534	9793
535	9003
536	8353
537	7363
538	7038
539	7816
540	9299
541	9531
542	8656
543	8575
544	8644
545	7913
546	7014
547	7801
548	9161
549	9599
550	8076
551	7427
552	7826
553	7857
554	7853
555	9325
556	9173
557	8119
558	6945
559	5981
560	5752
561	6377
562	6722
563	6641
564	6634
565	5970
566	4737
567	3702
568	3623
569	3107
570	4077
571	5850
572	6050
573	5870
574	6219
575	7088
576	6916
577	6299
578	6367
579	6855
580	5926
581	4396
582	3650
583	2982
584	3174
585	4304
586	4480
587	3746
588	3896
589	4347
590	4682
591	4393
592	3691
593	2907
594	2650
595	2553
596	2670
597	2221
598	1888
599	1747
600	2225
601	3044
602	3058
603	2593
604	2409
605	2176
606	2289
607	2929
608	3963
609	4639
610	3679
611	2990
612	2780
613	2924
614	3492
615	4189
616	4088
617	3458
618	2860
619	2878
620	2297
621	1700
622	1707
623	2152
624	3239
625	3733
626	3157
627	2889
628	2784
629	2879
630	3772
631	5466
632	6321
633	4548
634	3222
635	3965
636	4099
637	3365
638	3600
639	4272
640	4857
641	4137
642	2726
643	2545
644	2881
645	2941
646	2781
647	2603
648	2367
649	2179
650	2471
651	2207
652	1841
653	2053
654	2675
655	2889
656	2012
657	1666
658	2770
659	4995
660	5393
661	4183
662	3769
663	3800
664	3327
665	2735
666	2507
667	2324
668	4369
669	6311
670	5517
671	4782
672	3850
673	2894
674	2810
675	4108
676	5374
677	4688
678	3288
679	2124
680	1955
681	3316
682	4739
683	4726
684	3744
685	3094
686	2522
687	3363
688	4406
689	3783
690	2358
691	1501
692	1711
693	2311
694	2768
695	3416
696	4227
697	3712
698	2433
699	1963
700	2341
701	3133
702	3587
703	4108
704	3939
705	3108
706	2325
707	2206
708	2691
709	2818
710	2627
711	2795
712	2612
713	1831
714	1570
715	1906
716	2612
717	3620
718	4832
719	4124
720	3491
721	2736
722	3873
723	4976
724	3948
725	3146
726	4255
727	4816
728	5096
729	4853
730	4458
731	4021
732	3694
733	4659
734	5057
735	4682
736	4850
737	4636
738	5036
739	4485
740	3809
741	3669
742	4070
743	2749
744	1740
745	3178
746	4467
747	5294
748	6795
749	7029
750	5857
751	5503
752	5806
753	4134
754	2996
755	3806
756	4277
757	5040
758	4148
759	3665
760	5493
761	6836
762	5095
763	3862
764	4932
765	5912
766	6994
767	6761
768	5028
769	5275
770	7087
771	6033
772	5338
773	7534
774	8510
775	7746
776	8100
777	10864
778	10676
779	8518
780	6786
781	6328
782	6355
783	6581
784	8970
785	10141
786	9269
787	9425
788	10176
789	10341
790	12154
791	12308
792	10791
793	9191
794	8552
795	8881
796	9440
797	11549
798	12710
799	12264
800	9259
801	9930
802	10212
803	9982
804	11526
805	12646
806	12553
807	10935
808	9672
809	10559
810	11400
811	11746
812	11217
813	8842
814	10616
815	11736
816	10456
817	9771
818	9760
819	12029
820	11433
821	9094
822	9442
823	9448
824	11854
825	14367
826	13972
827	11875
828	9103
829	7603
830	6116
831	6889
832	8249
833	6993
834	6432
835	8905
836	11194
837	12206
838	10205
839	8529
840	8489
841	5734
842	4724
843	4020
844	4240
845	5156
846	5066
847	4616
848	3026
849	3000
850	4907
851	4661
852	3168
853	2927
854	2226
855	2952
856	3689
857	6096
858	7760
859	7800
860	6185
861	5535
862	5209
863	5167
864	4589
865	3332
866	3299
867	3897
868	4813
869	3766
870	2405
871	2404
872	2671
873	2437
874	2685
875	3032
876	4403
877	4429
878	2440
879	1725
880	1334
881	1837
882	1963
883	1639
884	1534
885	824
886	137
887	-174
888	946
889	1309
890	1244
891	1509
892	1746
893	2043
894	1867
895	2188
896	3474
897	3078
898	2291
899	1688
900	2339
901	2185
902	2307
903	2698
904	3136
905	2694
906	2219
907	1650
908	1354
909	1103
910	919
911	751
912	1427
913	1958
914	1089
915	1852
916	2554
917	1726
918	1604
919	2289
920	3307
921	2907
922	1793
923	1877
924	1598
925	1264
926	1064
927	2390
928	3585
929	2052
930	1769
931	1576
932	1729
933	1848
934	1436
935	1110
936	1067
937	1644
938	1820
939	1148
940	444
941	267
942	630
943	1174
944	1120
945	863
946	844
947	1018
948	1294
949	1162
950	1045
951	1316
952	1775
953	1866
954	930
955	1025
956	1288
957	1385
958	2367
959	1708
960	827
961	801
962	1353
963	2333
964	1618
965	1700
966	1398
967	1454
968	3675
969	2446
970	778
971	571
972	1115
973	1624
974	1220
975	1825
976	2090
977	1577
978	1925
979	1106
980	1663
981	2330
982	1150
983	747
984	928
985	1742
986	1813
987	924
988	621
989	614
990	1592
991	2573
992	1679
993	846
994	2144
995	3464
996	1984
997	1489
998	699
999	-209
1000	-191
1001	225
1002	663
1003	310
1004	257
1005	153
1006	338
1007	640
1008	784
1009	707
1010	1130
1011	1358
1012	1711
1013	3132
1014	2845
1015	887
1016	287
1017	162
1018	283
1019	520
1020	752
1021	790
1022	1143
1023	1177
1024	1159