1	1774
2	2911
3	4227
4	5508
5	6285
6	5977
7	5214
8	4345
9	3079
10	1991
11	1317
12	988
13	998
14	903
15	961
16	1218
17	1806
18	2097
19	2314
20	2063
21	1740
22	1755
23	1462
24	1078
25	970
26	1056
27	1156
28	1316
29	1249
30	1024
31	439
32	-2
33	-153
34	-54
35	102
36	476
37	745
38	900
39	1262
40	1567
41	1926
42	2201
43	2215
44	2007
45	2175
46	1712
47	1569
48	1658
49	1335
50	1483
51	1620
52	1315
53	1388
54	1291
55	1239
56	925
57	675
58	546
59	573
60	776
61	1287
62	2025
63	2605
64	2613
65	2448
66	2375
67	2709
68	3072
69	3052
70	2742
71	2486
72	2216
73	2113
74	1809
75	1800
76	1932
77	2479
78	3007
79	3436
80	4071
81	4410
82	4428
83	3962
84	3159
85	2554
86	2007
87	2111
88	2167
89	1979
90	1663
91	1757
92	1795
93	1618
94	1153
95	870
96	768
97	731
98	786
99	953
100	1388
101	1793
102	2101
103	2344
104	2025
105	1811
106	1844
107	2119
108	2288
109	2386
110	2178
111	1928
112	1855
113	1682
114	1555
115	1710
116	1919
117	2214
118	1814
119	1475
120	1083
121	715
122	611
123	432
124	476
125	668
126	1126
127	1686
128	2501
129	2589
130	2431
131	1964
132	2008
133	2078
134	1959
135	1834
136	1433
137	1214
138	1075
139	1204
140	1450
141	1446
142	1475
143	1582
144	1499
145	1689
146	2088
147	2990
148	3346
149	3143
150	2390
151	2130
152	2342
153	2501
154	2793
155	2843
156	2933
157	3170
158	2853
159	2440
160	1954
161	1534
162	1242
163	931
164	917
165	857
166	880
167	943
168	1595
169	2253
170	3072
171	3362
172	2900
173	2336
174	1795
175	1255
176	1158
177	1179
178	1358
179	1151
180	1064
181	972
182	780
183	504
184	324
185	702
186	1336
187	1773
188	1686
189	1604
190	1988
191	2144
192	2362
193	2227
194	2261
195	2105
196	1685
197	1544
198	1295
199	847
200	939
201	858
202	711
203	350
204	371
205	474
206	726
207	1111
208	1649
209	2603
210	3537
211	3697
212	2913
213	1877
214	1243
215	1288
216	1787
217	2280
218	2462
219	2376
220	2182
221	1901
222	1702
223	1975
224	2921
225	3849
226	3862
227	3309
228	2139
229	1796
230	1751
231	1745
232	1772
233	1449
234	1358
235	1818
236	2825
237	3445
238	3312
239	2620
240	2257
241	2494
242	2545
243	2460
244	2181
245	1892
246	2162
247	2511
248	2577
249	2254
250	2158
251	2156
252	2191
253	1847
254	1949
255	2117
256	2013
257	1930
258	1948
259	2115
260	1893
261	1783
262	1901
263	2134
264	2623
265	2813
266	2490
267	2317
268	2104
269	1760
270	1656
271	1756
272	2061
273	2207
274	2237
275	1973
276	2324
277	2433
278	2470
279	2539
280	2671
281	2791
282	2507
283	2253
284	2170
285	2540
286	3586
287	5834
288	8814
289	12009
290	14593
291	17405
292	19134
293	20102
294	20393
295	20868
296	20604
297	19061
298	17442
299	16223
300	15217
301	13745
302	12250
303	11224
304	10938
305	10449
306	9555
307	9176
308	9451
309	10662
310	12057
311	12429
312	11713
313	11502
314	11387
315	10273
316	8419
317	7297
318	7463
319	8115
320	8336
321	7394
322	6259
323	5659
324	5146
325	4861
326	5744
327	7346
328	9136
329	10911
330	13560
331	15078
332	14538
333	12070
334	9853
335	8444
336	7960
337	7994
338	8791
339	9499
340	9837
341	10149
342	9962
343	9096
344	8888
345	9485
346	9138
347	7485
348	6739
349	6896
350	7671
351	9181
352	10570
353	10641
354	9427
355	7890
356	7618
357	8435
358	9275
359	9360
360	9178
361	8812
362	8845
363	8651
364	8391
365	7305
366	6564
367	5785
368	5914
369	7086
370	8274
371	7946
372	6649
373	5533
374	5545
375	6122
376	6854
377	7743
378	7784
379	7022
380	6566
381	7244
382	8765
383	8708
384	7719
385	8088
386	9704
387	10541
388	10047
389	9383
390	9069
391	8566
392	7684
393	7667
394	8100
395	8426
396	8098
397	7514
398	8412
399	9072
400	8760
401	8220
402	7080
403	5769
404	5071
405	5535
406	6301
407	7255
408	9225
409	10614
410	10028
411	7474
412	5673
413	5377
414	6119
415	7553
416	9925
417	11122
418	10469
419	8971
420	8152
421	7255
422	6129
423	5189
424	5083
425	5475
426	6209
427	6614
428	6190
429	5571
430	4727
431	4264
432	3662
433	3364
434	3611
435	3663
436	3537
437	3950
438	5154
439	6846
440	8673
441	9352
442	8072
443	7150
444	6013
445	5305
446	5479
447	5289
448	5149
449	5784
450	6630
451	6825
452	6981
453	7260
454	7674
455	7524
456	6335
457	4398
458	3575
459	4226
460	5657
461	7264
462	6797
463	6315
464	6607
465	7926
466	9109
467	7909
468	4942
469	3799
470	3982
471	4727
472	5144
473	6206
474	7053
475	6412
476	5585
477	5741
478	7086
479	8228
480	7837
481	7017
482	5505
483	3919
484	3226
485	3661
486	5091
487	6404
488	6735
489	6200
490	5660
491	4979
492	4148
493	4829
494	5964
495	6100
496	5251
497	5061
498	5746
499	6066
500	5067
501	4480
502	5895
503	7168
504	7441
505	7787
506	6980
507	5782
508	5804
509	6371
510	6372
511	5674
512	5372
513	5860
514	7130
515	8407
516	9230
517	8562
518	7093
519	6440
520	5533
521	5014
522	5021
523	4311
524	3561
525	2814
526	2536
527	2951
528	4000
529	5263
530	6831
531	7482
532	8027
533	8934
534	8976
535	8821
536	7523
537	6253
538	5458
539	4691
540	3968
541	3583
542	4060
543	4825
544	4609
545	3755
546	4223
547	6147
548	5726
549	4769
550	4365
551	4546
552	4382
553	4194
554	3826
555	3708
556	4426
557	5318
558	5429
559	4614
560	4631
561	5641
562	6597
563	6764
564	6019
565	5847
566	5004
567	4289
568	4517
569	5208
570	5377
571	5083
572	4181
573	3328
574	3560
575	4015
576	3723
577	3991
578	5564
579	6762
580	6531
581	6192
582	6406
583	5656
584	3941
585	2805
586	2942
587	3864
588	4266
589	3547
590	4074
591	5094
592	5645
593	6167
594	6325
595	5226
596	4974
597	6385
598	8257
599	6939
600	4580
601	3053
602	2577
603	2921
604	4150
605	5543
606	6174
607	6590
608	6496
609	7226
610	9215
611	9634
612	9457
613	9325
614	9192
615	8559
616	7555
617	6332
618	4582
619	3295
620	3441
621	4738
622	5102
623	4449
624	4624
625	4731
626	4391
627	4373
628	5855
629	6385
630	5226
631	5250
632	6992
633	8239
634	7301
635	7283
636	6961
637	6492
638	5931
639	5446
640	5711
641	6191
642	6864
643	8288
644	10232
645	10624
646	9070
647	8462
648	9928
649	11391
650	10257
651	7730
652	6948
653	7208
654	6799
655	6545
656	7410
657	8198
658	8463
659	8582
660	9020
661	10715
662	11881
663	13311
664	13907
665	12291
666	11565
667	10878
668	9827
669	7744
670	6746
671	6840
672	5804
673	5774
674	7791
675	9513
676	9683
677	9071
678	9178
679	10217
680	11185
681	11455
682	11707
683	12670
684	12686
685	12510
686	12982
687	11628
688	10181
689	9256
690	8352
691	7111
692	6558
693	7037
694	9023
695	10166
696	10199
697	9965
698	9609
699	10774
700	11652
701	10513
702	10147
703	9869
704	9215
705	8800
706	8394
707	7199
708	6880
709	7178
710	7899
711	8843
712	8590
713	9717
714	11375
715	11084
716	10015
717	9276
718	9105
719	8730
720	8200
721	5761
722	4181
723	4414
724	4736
725	4601
726	3938
727	3455
728	3206
729	3213
730	3903
731	4554
732	6150
733	7279
734	8816
735	9011
736	7335
737	8799
738	10752
739	9910
740	8661
741	7940
742	6960
743	4801
744	4236
745	3886
746	3811
747	4638
748	5735
749	6694
750	7116
751	7091
752	5801
753	5970
754	7371
755	8262
756	10192
757	8311
758	5516
759	7187
760	9230
761	9270
762	8856
763	7867
764	5965
765	3968
766	3448
767	4077
768	4992
769	5085
770	5664
771	6132
772	5988
773	6105
774	6540
775	7661
776	7935
777	6670
778	7106
779	8072
780	7067
781	6555
782	6302
783	4219
784	3945
785	4043
786	3968
787	4088
788	3711
789	4649
790	4901
791	3950
792	4114
793	4266
794	4690
795	6250
796	8036
797	8409
798	7541
799	5915
800	4178
801	3204
802	3169
803	3882
804	3781
805	3709
806	4190
807	4544
808	3693
809	2467
810	2278
811	2350
812	1994
813	1748
814	2324
815	3132
816	5310
817	8362
818	10131
819	10331
820	8401
821	8208
822	8070
823	5627
824	4670
825	4318
826	3088
827	2841
828	3042
829	2759
830	2746
831	2747
832	2698
833	3000
834	3280
835	3069
836	3855
837	4127
838	4569
839	5691
840	6799
841	7825
842	5968
843	4409
844	4778
845	5596
846	5062
847	3724
848	2581
849	2324
850	3039
851	2955
852	3126
853	4190
854	4016
855	2716
856	2742
857	4364
858	6293
859	7987
860	7546
861	6697
862	6204
863	5807
864	3917
865	2589
866	2318
867	2395
868	1749
869	1293
870	2266
871	2705
872	1823
873	1657
874	1832
875	2214
876	3034
877	3085
878	3035
879	2918
880	3082
881	2876
882	3272
883	5337
884	5240
885	3998
886	5382
887	6835
888	4488
889	3102
890	2283
891	2776
892	3089
893	1929
894	2362
895	4328
896	2708
897	2258
898	1963
899	1924
900	3324
901	3524
902	3766
903	4618
904	3937
905	3973
906	5476
907	4977
908	3340
909	1974
910	2463
911	1703
912	1898
913	1887
914	1891
915	2231
916	1501
917	2168
918	2162
919	1008
920	723
921	1191
922	1950
923	1920
924	1997
925	3197
926	4630
927	7164
928	7762
929	5157
930	3749
931	2939
932	3118
933	2325
934	2723
935	3349
936	3469
937	2673
938	2122
939	1554
940	1998
941	2619
942	2314
943	2000
944	2832
945	3999
946	5155
947	4464
948	3371
949	3378
950	3162
951	4176
952	5935
953	7786
954	7229
955	4296
956	3065
957	2316
958	1201
959	987
960	1400
961	3714
962	3028
963	2042
964	2467
965	2791
966	3470
967	3585
968	2126
969	1530
970	2234
971	3652
972	3064
973	3935
974	3882
975	3181
976	4615
977	6671
978	5761
979	6312
980	4773
981	1927
982	1277
983	1089
984	1452
985	2815
986	2350
987	1496
988	2198
989	3795
990	1755
991	672
992	790
993	701
994	1097
995	2640
996	3563
997	3546
998	3301
999	4423
1000	4271
1001	3396
1002	2932
1003	1557
1004	911
1005	607
1006	821
1007	2088
1008	3320
1009	3803
1010	2854
1011	2539
1012	3043
1013	2678
1014	1682
1015	1416
1016	2334
1017	3830
1018	3057
1019	2041
1020	2406
1021	2759
1022	2550
1023	3631
1024	2597