1	1480
2	1908
3	2516
4	2700
5	2741
6	2521
7	2277
8	1776
9	1708
10	1634
11	1865
12	2105
13	2378
14	2320
15	2504
16	2257
17	2019
18	1561
19	1226
20	991
21	1107
22	1560
23	1924
24	2013
25	2121
26	2120
27	2024
28	1883
29	1477
30	1229
31	1389
32	1892
33	2136
34	2389
35	2510
36	2784
37	2757
38	2681
39	2734
40	2810
41	2369
42	2049
43	1655
44	2018
45	2845
46	3406
47	3365
48	2510
49	1546
50	1010
51	1301
52	1955
53	2775
54	3232
55	3110
56	2581
57	1723
58	1083
59	984
60	1189
61	1454
62	1852
63	2024
64	1875
65	1762
66	1728
67	2143
68	2577
69	2990
70	3043
71	2499
72	2129
73	2100
74	1919
75	1787
76	1811
77	2238
78	2699
79	3103
80	3528
81	4282
82	4319
83	3718
84	2857
85	1996
86	1543
87	1734
88	1782
89	1726
90	1617
91	1226
92	1144
93	1067
94	1318
95	1159
96	1200
97	1042
98	943
99	1426
100	1989
101	2215
102	2354
103	2683
104	3241
105	3787
106	3625
107	2790
108	2307
109	1841
110	1851
111	2087
112	2179
113	2048
114	2155
115	2892
116	3793
117	4251
118	3932
119	2924
120	2104
121	1867
122	2055
123	3048
124	4317
125	5378
126	5686
127	5287
128	4415
129	3775
130	3295
131	2626
132	2256
133	1966
134	1761
135	1847
136	1726
137	1548
138	1529
139	1401
140	1686
141	2457
142	3540
143	4480
144	4828
145	4711
146	4733
147	4753
148	5023
149	5367
150	5851
151	6247
152	6072
153	5087
154	3863
155	3207
156	3061
157	3054
158	3194
159	3366
160	3623
161	3513
162	3843
163	4611
164	5811
165	6891
166	7505
167	7632
168	7159
169	6563
170	6709
171	7807
172	8066
173	7656
174	6890
175	6449
176	6983
177	7455
178	7962
179	9218
180	10839
181	11627
182	10550
183	9101
184	7248
185	6376
186	5692
187	5935
188	6798
189	7824
190	8449
191	8865
192	9104
193	10098
194	11050
195	12140
196	12963
197	13837
198	14283
199	14400
200	14456
201	14612
202	13702
203	12055
204	10027
205	9322
206	9633
207	10679
208	11801
209	13520
210	14684
211	15218
212	14296
213	12776
214	11633
215	11245
216	10732
217	10798
218	10136
219	9951
220	9643
221	9658
222	9898
223	9637
224	9038
225	8459
226	8296
227	8718
228	9224
229	8604
230	8390
231	8572
232	8793
233	7927
234	6478
235	5284
236	4459
237	3879
238	3940
239	4926
240	6680
241	8624
242	9111
243	8273
244	6991
245	6611
246	6830
247	6521
248	5507
249	4676
250	4541
251	4562
252	4472
253	4905
254	5567
255	5660
256	5561
257	5455
258	5375
259	5043
260	4628
261	4445
262	3961
263	3481
264	3714
265	4026
266	4757
267	5359
268	5796
269	5551
270	5506
271	5990
272	6067
273	5718
274	5311
275	4892
276	4234
277	3506
278	2866
279	2670
280	3279
281	4225
282	4918
283	4783
284	4439
285	5350
286	5936
287	5982
288	5173
289	4342
290	4543
291	4828
292	5009
293	4591
294	4087
295	4079
296	3945
297	3195
298	2884
299	3017
300	3524
301	4542
302	5517
303	6325
304	6159
305	6085
306	6987
307	8594
308	9810
309	9096
310	6995
311	6011
312	5466
313	5338
314	5144
315	5374
316	5331
317	5113
318	5193
319	5927
320	6637
321	6998
322	6612
323	6316
324	6477
325	6862
326	7900
327	8612
328	7969
329	7044
330	6146
331	5086
332	4663
333	5079
334	6108
335	6670
336	6892
337	7334
338	8271
339	8597
340	8217
341	7582
342	7434
343	7685
344	7981
345	8831
346	9470
347	9975
348	10283
349	9577
350	7986
351	6768
352	6823
353	7280
354	7217
355	7661
356	8194
357	8814
358	9651
359	9486
360	8946
361	8418
362	8175
363	7616
364	6352
365	5169
366	5082
367	5413
368	5658
369	5922
370	6740
371	8157
372	9413
373	9911
374	9827
375	9356
376	10140
377	11089
378	11023
379	10086
380	9461
381	9550
382	10259
383	10968
384	11551
385	11252
386	10190
387	9478
388	10011
389	11024
390	12402
391	13554
392	13608
393	13758
394	14614
395	14500
396	13277
397	12166
398	13632
399	15993
400	16434
401	15306
402	15114
403	15745
404	14745
405	12444
406	11879
407	13486
408	15067
409	14125
410	13617
411	13279
412	12898
413	11915
414	11522
415	11946
416	14833
417	18466
418	20742
419	19670
420	18865
421	17830
422	17540
423	18023
424	18772
425	19442
426	20447
427	19796
428	17626
429	15143
430	14577
431	14865
432	15927
433	16451
434	16823
435	16942
436	16411
437	14788
438	13957
439	13168
440	12630
441	12658
442	13175
443	13268
444	13670
445	13176
446	13410
447	15145
448	17696
449	17664
450	16562
451	16806
452	17272
453	16121
454	13914
455	12688
456	13937
457	15990
458	18530
459	22389
460	23012
461	19575
462	17643
463	18027
464	18555
465	17968
466	18170
467	19205
468	18894
469	18143
470	17432
471	17161
472	16485
473	17141
474	18463
475	19698
476	20051
477	19540
478	21211
479	24049
480	25907
481	28175
482	26911
483	24507
484	24749
485	26732
486	27727
487	26547
488	25088
489	24656
490	25911
491	26578
492	26342
493	28625
494	29365
495	26303
496	22998
497	23198
498	22565
499	19932
500	19545
501	20113
502	19515
503	19701
504	20470
505	18215
506	14044
507	11925
508	11995
509	13930
510	15303
511	13921
512	11884
513	11760
514	13521
515	14154
516	12238
517	10120
518	9870
519	9479
520	9535
521	9331
522	10159
523	11037
524	10333
525	10185
526	10616
527	11336
528	12917
529	14247
530	13807
531	11231
532	8907
533	7892
534	6491
535	5468
536	5966
537	6840
538	7993
539	8262
540	8351
541	8944
542	8671
543	7683
544	7678
545	8470
546	8507
547	8225
548	7603
549	7554
550	6550
551	5492
552	6001
553	7266
554	7853
555	8939
556	9421
557	8083
558	6661
559	6366
560	6635
561	7110
562	7832
563	7087
564	6243
565	6377
566	6528
567	7465
568	9092
569	9371
570	8757
571	6865
572	4767
573	4052
574	3596
575	3295
576	4399
577	6658
578	7689
579	7694
580	8882
581	8584
582	6609
583	4193
584	2517
585	2103
586	3254
587	5858
588	7062
589	7232
590	7676
591	6983
592	5205
593	3261
594	2341
595	2677
596	3868
597	3763
598	3232
599	2942
600	3156
601	3620
602	3990
603	4015
604	3879
605	3213
606	2835
607	2034
608	1183
609	1527
610	1915
611	2106
612	2913
613	4184
614	4136
615	3932
616	4026
617	3591
618	3004
619	3093
620	3416
621	3275
622	3047
623	3183
624	2889
625	2011
626	2240
627	2252
628	1970
629	2121
630	2560
631	3061
632	2635
633	1778
634	1999
635	3047
636	3156
637	3294
638	3687
639	3628
640	2961
641	2315
642	1753
643	1540
644	1556
645	1626
646	2435
647	2870
648	2748
649	2304
650	2222
651	2649
652	3207
653	3458
654	3388
655	3821
656	4353
657	3862
658	2773
659	2635
660	3291
661	3135
662	2327
663	1841
664	2131
665	2521
666	2874
667	3847
668	4909
669	3819
670	2606
671	2010
672	1876
673	2736
674	4057
675	4786
676	5645
677	5590
678	3611
679	2655
680	2758
681	3899
682	4593
683	3679
684	3795
685	4838
686	3826
687	2221
688	1662
689	2129
690	2084
691	1970
692	2150
693	2023
694	1348
695	1089
696	1954
697	3109
698	3799
699	3428
700	3634
701	4180
702	3644
703	3177
704	2578
705	3137
706	4296
707	4665
708	4565
709	4108
710	3371
711	2539
712	2387
713	2867
714	3168
715	2665
716	2288
717	3066
718	4393
719	4569
720	3976
721	2374
722	1439
723	1269
724	1327
725	2446
726	2632
727	2004
728	1848
729	2484
730	2902
731	2556
732	2897
733	3380
734	3380
735	2964
736	2813
737	3079
738	3802
739	4265
740	3871
741	3328
742	4011
743	3475
744	3920
745	4115
746	3051
747	3010
748	4106
749	4272
750	3668
751	3263
752	3116
753	3186
754	3197
755	4361
756	6133
757	7938
758	7602
759	7200
760	9248
761	9992
762	8316
763	9415
764	9856
765	8064
766	6908
767	7034
768	9156
769	10407
770	11203
771	8415
772	6682
773	7542
774	10361
775	14060
776	11973
777	10674
778	9966
779	9646
780	10613
781	10053
782	9588
783	9875
784	10211
785	10503
786	9489
787	10312
788	10302
789	10559
790	10552
791	10789
792	9865
793	12550
794	12323
795	10940
796	9173
797	8292
798	9882
799	9387
800	8198
801	9394
802	9562
803	10742
804	12399
805	13335
806	13790
807	11442
808	8737
809	8594
810	8591
811	7950
812	8110
813	8790
814	10416
815	11775
816	13404
817	12230
818	12831
819	13543
820	12624
821	10399
822	10109
823	9478
824	9974
825	11332
826	9425
827	8940
828	11057
829	12457
830	10983
831	9758
832	9801
833	9149
834	8483
835	8284
836	8133
837	8125
838	7097
839	6011
840	4480
841	4266
842	5331
843	5012
844	5225
845	4291
846	3346
847	3135
848	3472
849	2464
850	1928
851	2176
852	2595
853	3083
854	3403
855	3597
856	4244
857	4270
858	3738
859	3785
860	3434
861	2690
862	3631
863	5700
864	4788
865	3288
866	4298
867	3247
868	2564
869	3047
870	3205
871	2497
872	2246
873	1482
874	1260
875	2053
876	2955
877	3247
878	4084
879	2820
880	2164
881	2155
882	2236
883	2919
884	2053
885	2040
886	1916
887	743
888	785
889	2245
890	3817
891	4474
892	3535
893	2360
894	2147
895	3533
896	3208
897	1561
898	1631
899	1900
900	2353
901	1829
902	2550
903	2802
904	2248
905	2875
906	3500
907	3513
908	3000
909	2230
910	2697
911	1641
912	1542
913	2679
914	2641
915	3056
916	2799
917	1748
918	950
919	1022
920	1838
921	3257
922	2778
923	968
924	1094
925	1713
926	2265
927	2416
928	2286
929	2180
930	2784
931	3660
932	2502
933	1350
934	1426
935	1156
936	1275
937	1973
938	2579
939	3288
940	3049
941	1921
942	1006
943	552
944	389
945	428
946	1072
947	934
948	654
949	1027
950	2188
951	2069
952	590
953	573
954	1356
955	1147
956	1870
957	2107
958	2438
959	2995
960	1681
961	791
962	1431
963	1776
964	1689
965	1820
966	1999
967	2010
968	2597
969	2950
970	2289
971	1548
972	815
973	1091
974	785
975	1267
976	3250
977	3491
978	1904
979	898
980	443
981	541
982	873
983	854
984	1356
985	1974
986	2123
987	2905
988	3071
989	2155
990	1823
991	1422
992	1514
993	737
994	776
995	1428
996	1709
997	1134
998	1298
999	1276
1000	1416
1001	1015
1002	795
1003	1441
1004	2762
1005	3469
1006	5374
1007	2888
1008	2022
1009	1977
1010	1961
1011	2472
1012	2931
1013	2404
1014	1233
1015	1803
1016	2322
1017	1882
1018	2748
1019	1671
1020	696
1021	425
1022	870
1023	1408
1024	574