1	1998
2	1894
3	2226
4	2729
5	3140
6	3361
7	3464
8	2998
9	2878
10	2945
11	3059
12	2821
13	2401
14	2003
15	2235
16	2692
17	3106
18	3177
19	3213
20	2981
21	3060
22	3296
23	3194
24	2953
25	3070
26	3260
27	3519
28	3511
29	3115
30	2694
31	2236
32	1922
33	1858
34	2200
35	2440
36	2632
37	2480
38	2241
39	2640
40	3218
41	3846
42	4303
43	3965
44	3195
45	2630
46	2010
47	1873
48	1826
49	2079
50	2017
51	1927
52	1618
53	1613
54	2195
55	3130
56	4185
57	4693
58	4348
59	3536
60	2606
61	2187
62	2120
63	2316
64	2378
65	2338
66	2101
67	1902
68	1916
69	2116
70	2094
71	1959
72	1864
73	2177
74	2688
75	3411
76	3650
77	3484
78	3060
79	2649
80	2470
81	2921
82	3233
83	3441
84	3161
85	2584
86	2022
87	1817
88	1819
89	1774
90	2339
91	2962
92	3479
93	3381
94	3127
95	2554
96	2615
97	2571
98	2372
99	2466
100	2827
101	2820
102	2678
103	2927
104	3254
105	3732
106	3997
107	3766
108	3195
109	2243
110	1600
111	1466
112	1516
113	1790
114	2154
115	2413
116	2441
117	1888
118	1603
119	1931
120	2737
121	3541
122	3877
123	3860
124	3831
125	4281
126	4878
127	5029
128	4658
129	4324
130	3985
131	3806
132	3872
133	3270
134	2979
135	3109
136	4225
137	5445
138	6599
139	7424
140	7692
141	7866
142	7491
143	7312
144	6680
145	6252
146	6575
147	6894
148	7812
149	7995
150	7599
151	6704
152	6219
153	5585
154	5052
155	4776
156	4532
157	4345
158	4612
159	4624
160	4766
161	5139
162	5778
163	6213
164	6439
165	6619
166	7261
167	7137
168	7023
169	6472
170	6219
171	5809
172	5823
173	6533
174	6979
175	7498
176	8387
177	8981
178	8773
179	8840
180	8704
181	8706
182	8450
183	8436
184	8344
185	8444
186	8285
187	7861
188	7378
189	7732
190	9209
191	10383
192	10032
193	8642
194	7330
195	7036
196	7141
197	7500
198	7861
199	8167
200	8050
201	8073
202	8062
203	9134
204	10207
205	11174
206	11247
207	10646
208	10248
209	10477
210	10507
211	10549
212	10388
213	9879
214	9813
215	10560
216	10992
217	10891
218	9530
219	8977
220	8913
221	9714
222	9650
223	8857
224	7930
225	7374
226	7620
227	7789
228	7773
229	6515
230	5048
231	4336
232	4774
233	6413
234	7294
235	6849
236	6397
237	6279
238	7058
239	7835
240	7956
241	7940
242	7012
243	7083
244	7690
245	8345
246	8300
247	8234
248	7872
249	7571
250	7002
251	6623
252	6252
253	5989
254	5468
255	4475
256	4197
257	4543
258	5416
259	6528
260	6693
261	6801
262	6682
263	6020
264	6302
265	7115
266	7237
267	6683
268	6185
269	6152
270	6256
271	6982
272	8209
273	8980
274	8851
275	7531
276	5845
277	4545
278	4599
279	4890
280	5375
281	6013
282	6806
283	6884
284	6506
285	6634
286	6998
287	6901
288	6247
289	5516
290	5811
291	6613
292	7073
293	6929
294	6974
295	7168
296	6876
297	6180
298	5329
299	6182
300	7924
301	8878
302	7986
303	6399
304	5691
305	6517
306	7882
307	8521
308	7609
309	6133
310	5388
311	5988
312	6144
313	6023
314	5804
315	6102
316	5873
317	5735
318	5383
319	5926
320	7025
321	7820
322	7488
323	6431
324	5166
325	4133
326	3896
327	4760
328	6785
329	9091
330	9298
331	8172
332	6924
333	6663
334	7276
335	8153
336	9011
337	9196
338	8512
339	7764
340	7354
341	6852
342	6607
343	6144
344	6667
345	8188
346	9622
347	9527
348	8756
349	7802
350	7004
351	6845
352	7650
353	9040
354	9551
355	9263
356	8337
357	8606
358	10086
359	10053
360	9018
361	8163
362	8000
363	7727
364	8238
365	8470
366	6957
367	5008
368	5121
369	7050
370	8324
371	8199
372	8130
373	9192
374	10264
375	10327
376	10484
377	10796
378	10043
379	9182
380	9423
381	9511
382	8832
383	8783
384	10461
385	12018
386	13080
387	12554
388	11217
389	10609
390	10646
391	10491
392	9588
393	9575
394	9722
395	9305
396	9222
397	9203
398	9719
399	9764
400	10576
401	10816
402	11834
403	13493
404	14699
405	14689
406	15151
407	15619
408	15876
409	15492
410	15495
411	14679
412	15007
413	15378
414	15080
415	15817
416	17416
417	17345
418	18234
419	18882
420	17537
421	13687
422	12395
423	13311
424	13927
425	14591
426	16603
427	18500
428	19979
429	19922
430	19181
431	17621
432	16994
433	17104
434	17687
435	17714
436	15920
437	13690
438	12720
439	13700
440	15565
441	16328
442	16121
443	16148
444	16964
445	17158
446	16728
447	16162
448	17160
449	17632
450	16317
451	15953
452	16311
453	17900
454	19191
455	19165
456	17202
457	16903
458	16915
459	15778
460	14608
461	14668
462	14209
463	14199
464	15840
465	17462
466	18728
467	20802
468	20837
469	20021
470	19878
471	22453
472	23376
473	22415
474	22413
475	22966
476	22621
477	21881
478	20964
479	19591
480	17921
481	18015
482	19139
483	21370
484	23796
485	23440
486	21549
487	19858
488	18610
489	18849
490	20605
491	20939
492	19297
493	18517
494	19027
495	19886
496	19332
497	18587
498	18737
499	17572
500	17077
501	18106
502	18836
503	18252
504	18298
505	18353
506	20765
507	24276
508	24843
509	20814
510	18231
511	17790
512	16031
513	15120
514	15454
515	15131
516	13163
517	11672
518	11595
519	11156
520	10494
521	10034
522	10981
523	11076
524	10208
525	9040
526	9255
527	11447
528	12528
529	11528
530	9380
531	7890
532	7549
533	8734
534	9502
535	9245
536	9327
537	9534
538	8904
539	7806
540	7679
541	8303
542	8574
543	7950
544	6958
545	7193
546	7369
547	7252
548	7190
549	7177
550	6409
551	6167
552	6944
553	7519
554	7179
555	7476
556	7094
557	7143
558	7113
559	7270
560	8243
561	8205
562	7115
563	6788
564	8342
565	9077
566	7900
567	7065
568	7333
569	5956
570	4842
571	4344
572	4373
573	5410
574	6729
575	6744
576	5419
577	5115
578	5581
579	5587
580	5623
581	5543
582	5557
583	5072
584	4510
585	3519
586	3471
587	5056
588	5871
589	4905
590	4410
591	4575
592	5245
593	5157
594	5241
595	4530
596	3759
597	3451
598	3469
599	4282
600	4813
601	5502
602	6932
603	7028
604	5404
605	3786
606	3945
607	4401
608	3899
609	5428
610	6228
611	5562
612	5169
613	4854
614	3646
615	2444
616	2621
617	4276
618	6962
619	7257
620	4818
621	3785
622	5169
623	5892
624	4580
625	3592
626	4017
627	3854
628	3176
629	3253
630	2753
631	2087
632	1961
633	2956
634	4280
635	5597
636	4437
637	3559
638	3543
639	4735
640	6500
641	7127
642	5825
643	5372
644	5645
645	5177
646	4665
647	5065
648	5667
649	4914
650	4184
651	4020
652	4380
653	4578
654	5251
655	5490
656	5343
657	5645
658	5110
659	4914
660	4950
661	4391
662	3659
663	2966
664	2951
665	3317
666	3807
667	3901
668	4110
669	3566
670	3102
671	3913
672	5157
673	5239
674	4742
675	4249
676	4213
677	3893
678	2958
679	2170
680	2537
681	4285
682	7473
683	8847
684	7178
685	5456
686	4778
687	4010
688	3464
689	3390
690	4027
691	3542
692	2921
693	3532
694	4915
695	5911
696	6420
697	5922
698	4318
699	2831
700	3064
701	2640
702	2138
703	2260
704	2087
705	1627
706	2159
707	3491
708	4221
709	3968
710	3317
711	4128
712	5112
713	4939
714	5205
715	4767
716	4342
717	5391
718	7084
719	6867
720	6240
721	5540
722	3912
723	4020
724	6029
725	7365
726	6380
727	5102
728	4172
729	4360
730	6540
731	7707
732	6448
733	6821
734	6588
735	4918
736	4897
737	6211
738	6651
739	6476
740	8766
741	11678
742	10328
743	6606
744	4980
745	4709
746	5758
747	7657
748	6936
749	5757
750	5515
751	8074
752	10040
753	8832
754	8075
755	7779
756	6873
757	6091
758	5590
759	7876
760	8413
761	8294
762	8442
763	8679
764	7042
765	6205
766	5477
767	5785
768	7420
769	7651
770	6546
771	5855
772	6052
773	7577
774	7831
775	6714
776	7219
777	9013
778	10870
779	12286
780	11461
781	9086
782	7806
783	7796
784	7654
785	7083
786	7006
787	7240
788	7173
789	6415
790	6124
791	8641
792	8829
793	8649
794	8121
795	8444
796	8784
797	9613
798	9082
799	9337
800	9845
801	9142
802	8359
803	8610
804	7403
805	8568
806	7807
807	6785
808	8360
809	9095
810	8850
811	8198
812	7918
813	9676
814	9063
815	7362
816	7573
817	7697
818	7491
819	6712
820	7283
821	8788
822	8009
823	7810
824	8487
825	8415
826	9275
827	8512
828	5372
829	5089
830	6855
831	7981
832	6747
833	5451
834	5063
835	6027
836	5316
837	6135
838	6721
839	7344
840	6498
841	4117
842	3234
843	3626
844	4591
845	5114
846	5033
847	5010
848	5138
849	4528
850	3966
851	4499
852	3593
853	2802
854	3198
855	4374
856	3572
857	3188
858	2833
859	2570
860	2574
861	2212
862	3100
863	5379
864	5461
865	4204
866	3476
867	3048
868	1751
869	1486
870	1737
871	2163
872	2772
873	3438
874	4039
875	3616
876	3581
877	5394
878	5210
879	3667
880	2577
881	4018
882	3457
883	2597
884	3662
885	4497
886	4254
887	5779
888	5615
889	4272
890	2448
891	2625
892	4446
893	4075
894	3313
895	5533
896	5605
897	4148
898	2978
899	2085
900	2986
901	2819
902	2803
903	2585
904	2295
905	2823
906	2927
907	2307
908	1649
909	1472
910	1913
911	2302
912	2010
913	1880
914	2144
915	2550
916	3362
917	2015
918	1147
919	1354
920	2045
921	1601
922	1827
923	2783
924	4322
925	4103
926	4068
927	4594
928	3242
929	2747
930	4260
931	4327
932	3367
933	2790
934	2381
935	1919
936	2617
937	2527
938	3077
939	3302
940	2848
941	2248
942	1837
943	1669
944	2099
945	3363
946	3407
947	1830
948	1071
949	1436
950	2047
951	2666
952	1759
953	1231
954	1242
955	1591
956	2885
957	2359
958	2015
959	2059
960	1171
961	1192
962	2568
963	1939
964	685
965	1181
966	3058
967	2622
968	2637
969	4020
970	5133
971	3556
972	1948
973	2487
974	1807
975	840
976	1157
977	1930
978	3041
979	3836
980	4512
981	2519
982	2825
983	2457
984	2752
985	1556
986	578
987	1137
988	2610
989	3297
990	3195
991	2490
992	1805
993	1839
994	3550
995	4178
996	3889
997	3434
998	1719
999	570
1000	1325
1001	1641
1002	1828
1003	2232
1004	2664
1005	2545
1006	1551
1007	1649
1008	1586
1009	904
1010	460
1011	746
1012	1330
1013	1058
1014	818
1015	1200
1016	2394
1017	3051
1018	2788
1019	1434
1020	806
1021	1202
1022	1690
1023	1664
1024	1443