1	3852
2	4290
3	4718
4	5247
5	6058
6	6786
7	7246
8	6934
9	6582
10	6428
11	6808
12	7317
13	7345
14	6603
15	6007
16	5505
17	5404
18	5892
19	6624
20	7342
21	7762
22	7672
23	6796
24	6273
25	6190
26	5968
27	5820
28	5539
29	4931
30	4737
31	4524
32	4246
33	4236
34	4467
35	5089
36	5805
37	5866
38	5548
39	5270
40	5479
41	5768
42	6202
43	5969
44	6093
45	6891
46	7333
47	6824
48	6171
49	5590
50	5303
51	5445
52	5711
53	6198
54	6498
55	6629
56	6528
57	5924
58	4887
59	4278
60	4068
61	4474
62	5049
63	5587
64	5773
65	6358
66	6876
67	7044
68	6748
69	6143
70	5324
71	4944
72	5587
73	6847
74	7317
75	6686
76	5291
77	4291
78	4138
79	4710
80	5501
81	6010
82	5799
83	5397
84	5037
85	4691
86	4312
87	4208
88	4434
89	4733
90	5612
91	6080
92	6387
93	6561
94	6977
95	6897
96	6875
97	6972
98	6929
99	7676
100	8649
101	8988
102	9299
103	9279
104	8767
105	7955
106	7289
107	6959
108	6742
109	6219
110	5889
111	5699
112	5958
113	6709
114	8144
115	9392
116	10175
117	10190
118	9986
119	9424
120	8824
121	8398
122	7298
123	6291
124	5414
125	5713
126	6923
127	8760
128	10100
129	10775
130	10576
131	9716
132	9067
133	8388
134	7946
135	7797
136	8256
137	9187
138	9888
139	9982
140	9736
141	9020
142	7895
143	7170
144	6365
145	5521
146	4952
147	3975
148	3505
149	3677
150	4539
151	5934
152	8122
153	9777
154	10908
155	11142
156	10709
157	10128
158	9497
159	8842
160	8516
161	8091
162	8080
163	8495
164	9245
165	9639
166	9703
167	9545
168	9768
169	9818
170	10038
171	10600
172	11403
173	12611
174	12910
175	12687
176	12032
177	11616
178	11228
179	11972
180	12485
181	12707
182	11411
183	10286
184	9497
185	10145
186	11563
187	12791
188	13347
189	13180
190	12517
191	11349
192	10094
193	9606
194	9685
195	11021
196	12036
197	12838
198	12833
199	12621
200	12740
201	12527
202	11492
203	10507
204	10558
205	10929
206	11403
207	11298
208	10841
209	10401
210	9971
211	10668
212	11887
213	13095
214	13202
215	12693
216	12028
217	11809
218	11020
219	10852
220	10882
221	11582
222	12045
223	13274
224	14864
225	17056
226	17276
227	15850
228	14392
229	12986
230	12738
231	12529
232	12384
233	11564
234	10178
235	9397
236	9355
237	9618
238	10188
239	11043
240	11894
241	12422
242	12612
243	12775
244	13293
245	13392
246	12133
247	10001
248	8082
249	7357
250	7436
251	8363
252	9386
253	11257
254	12299
255	11962
256	11215
257	11024
258	11677
259	12118
260	11818
261	11552
262	11508
263	11364
264	11344
265	11042
266	10896
267	11231
268	12348
269	12947
270	11723
271	10783
272	11049
273	11972
274	12573
275	12144
276	11887
277	11649
278	11662
279	11166
280	10546
281	10905
282	12123
283	14042
284	14739
285	13920
286	11366
287	9370
288	8548
289	8134
290	7270
291	6603
292	6928
293	8029
294	9689
295	9964
296	8856
297	8113
298	9198
299	11308
300	12671
301	13231
302	13459
303	13526
304	12632
305	11424
306	10246
307	10066
308	10110
309	10802
310	12817
311	14584
312	15250
313	15136
314	13818
315	11863
316	10565
317	9477
318	8372
319	8349
320	9966
321	11310
322	11637
323	11606
324	11620
325	11368
326	11471
327	11584
328	11451
329	12079
330	12755
331	13258
332	13621
333	13039
334	12390
335	12815
336	12949
337	12528
338	11134
339	9403
340	8017
341	7484
342	7876
343	8901
344	10158
345	11043
346	10807
347	11239
348	12564
349	14163
350	14202
351	13634
352	13051
353	13146
354	12599
355	11702
356	11120
357	11634
358	12907
359	14227
360	15042
361	13683
362	12236
363	12282
364	12113
365	12055
366	11788
367	11250
368	9960
369	9364
370	10213
371	12266
372	13824
373	14990
374	14840
375	11931
376	9418
377	9572
378	11057
379	12273
380	13548
381	14610
382	13992
383	12656
384	12775
385	13018
386	13370
387	13865
388	15229
389	15000
390	14071
391	13895
392	14046
393	13171
394	11467
395	11066
396	12971
397	15991
398	18865
399	19132
400	17859
401	16599
402	17308
403	19130
404	19898
405	19119
406	17604
407	15281
408	14057
409	14514
410	15934
411	16628
412	16764
413	15985
414	14365
415	13071
416	13715
417	15949
418	18660
419	19209
420	18078
421	16736
422	16269
423	15407
424	14240
425	14168
426	16361
427	18419
428	18912
429	16459
430	14765
431	13742
432	13682
433	14073
434	14244
435	14252
436	13900
437	14348
438	16235
439	18776
440	20520
441	20238
442	19532
443	19378
444	18672
445	17457
446	17392
447	16633
448	14836
449	12540
450	10744
451	10085
452	8972
453	8570
454	9542
455	10361
456	11583
457	13647
458	15103
459	16030
460	15471
461	14174
462	13964
463	15506
464	16994
465	17345
466	17700
467	17776
468	17062
469	17075
470	17794
471	18432
472	18260
473	17981
474	17324
475	17056
476	17555
477	18864
478	19108
479	18662
480	19852
481	20855
482	18601
483	17276
484	17655
485	18229
486	19123
487	19460
488	17600
489	15897
490	16270
491	16422
492	15136
493	14941
494	15616
495	15910
496	16254
497	16541
498	18049
499	17271
500	14763
501	13982
502	13984
503	12561
504	11077
505	10566
506	10817
507	11107
508	11539
509	13041
510	15309
511	16182
512	14141
513	11592
514	10453
515	10610
516	10761
517	9998
518	9834
519	9856
520	9890
521	9707
522	10175
523	11024
524	11236
525	9740
526	7125
527	6813
528	8057
529	8643
530	8200
531	7891
532	8652
533	10581
534	12113
535	13161
536	14075
537	13797
538	12009
539	10744
540	10528
541	10147
542	10176
543	11936
544	12556
545	11671
546	8752
547	6576
548	6592
549	8505
550	9204
551	8205
552	8109
553	9130
554	9370
555	7941
556	6149
557	5782
558	6394
559	7485
560	8444
561	9025
562	10510
563	11356
564	10538
565	10210
566	10159
567	9229
568	9778
569	9180
570	8545
571	9205
572	11554
573	13561
574	13305
575	11642
576	9387
577	7672
578	6953
579	7855
580	8310
581	7934
582	8285
583	8500
584	8812
585	9450
586	9712
587	9604
588	8433
589	7942
590	8417
591	9570
592	11346
593	11249
594	10252
595	9595
596	9492
597	9690
598	9984
599	10107
600	11077
601	11192
602	11443
603	13361
604	13139
605	10483
606	9675
607	9914
608	8939
609	10572
610	11356
611	10223
612	9501
613	9174
614	8677
615	9179
616	8149
617	7039
618	7320
619	7868
620	9077
621	9510
622	8626
623	7674
624	8378
625	9753
626	10318
627	9077
628	8659
629	9489
630	10534
631	10093
632	7968
633	6288
634	5022
635	4871
636	5115
637	7041
638	8020
639	6793
640	5562
641	6611
642	9001
643	9084
644	8355
645	9087
646	9894
647	9120
648	6678
649	5915
650	6674
651	6264
652	5835
653	5401
654	5862
655	6565
656	7268
657	8545
658	8066
659	6506
660	5260
661	5447
662	7406
663	8602
664	8006
665	6770
666	6466
667	6125
668	6139
669	6992
670	8165
671	9294
672	8647
673	7206
674	5752
675	5374
676	6403
677	7298
678	9399
679	11658
680	10705
681	9158
682	9324
683	8216
684	7236
685	7535
686	6641
687	5988
688	6133
689	7969
690	9167
691	9556
692	8479
693	8588
694	8570
695	7560
696	6887
697	7527
698	7345
699	6443
700	6239
701	6117
702	7448
703	10105
704	9478
705	8261
706	8531
707	10454
708	11792
709	10796
710	9950
711	10033
712	9489
713	8118
714	9444
715	11302
716	11415
717	10740
718	11135
719	12547
720	13118
721	12630
722	13015
723	12905
724	13122
725	13013
726	12833
727	12828
728	12465
729	10479
730	9445
731	11081
732	12346
733	11343
734	10446
735	9613
736	8551
737	9644
738	13140
739	16894
740	16780
741	13539
742	12409
743	13372
744	13478
745	12207
746	11873
747	12404
748	13581
749	14150
750	14155
751	14544
752	12573
753	11013
754	11505
755	12355
756	11788
757	11654
758	11320
759	11412
760	11182
761	13011
762	15169
763	14803
764	12773
765	10946
766	10302
767	8915
768	7313
769	6404
770	6750
771	9961
772	11865
773	13807
774	14571
775	14800
776	15109
777	12521
778	10696
779	9411
780	10135
781	11752
782	13146
783	13173
784	12018
785	12059
786	11228
787	10216
788	10374
789	10909
790	13799
791	15448
792	11523
793	7723
794	8363
795	9715
796	11863
797	14240
798	14692
799	15161
800	12633
801	10065
802	8075
803	7398
804	7339
805	7390
806	6753
807	6973
808	7597
809	8567
810	8473
811	8676
812	11147
813	12646
814	11916
815	11106
816	9528
817	7915
818	7283
819	7598
820	9956
821	12899
822	11158
823	8970
824	10089
825	12266
826	10713
827	7838
828	5342
829	4901
830	5763
831	8436
832	8218
833	7964
834	9134
835	9208
836	8516
837	7809
838	7904
839	8589
840	7670
841	6601
842	6298
843	7069
844	9704
845	8558
846	6631
847	6519
848	7231
849	8655
850	8454
851	7787
852	6648
853	6650
854	7669
855	7090
856	6546
857	8236
858	8539
859	7466
860	6876
861	8153
862	9561
863	8507
864	6490
865	4365
866	2547
867	2616
868	3408
869	2864
870	2856
871	3618
872	4077
873	4637
874	4641
875	4609
876	5718
877	5336
878	7836
879	9835
880	9433
881	5608
882	4340
883	3968
884	4468
885	4607
886	6013
887	7103
888	8132
889	6694
890	4397
891	3634
892	3710
893	5301
894	5436
895	5239
896	5439
897	5823
898	5487
899	4293
900	5314
901	5265
902	5727
903	7144
904	4769
905	2811
906	3164
907	3866
908	3690
909	4389
910	4637
911	3630
912	3808
913	4254
914	4952
915	3857
916	3566
917	6336
918	6473
919	4106
920	3390
921	3488
922	5161
923	5496
924	6225
925	5494
926	5327
927	5605
928	4945
929	4865
930	4084
931	2860
932	2612
933	4293
934	6191
935	4087
936	3986
937	5565
938	5054
939	4076
940	5772
941	6342
942	4944
943	5378
944	5168
945	4463
946	4672
947	5283
948	6600
949	7366
950	6088
951	5007
952	4723
953	4012
954	3478
955	3226
956	3564
957	3591
958	4532
959	6383
960	7489
961	5365
962	4730
963	3320
964	2059
965	2324
966	3040
967	4610
968	4941
969	3123
970	2712
971	2678
972	3178
973	4467
974	4945
975	5174
976	4809
977	3708
978	3327
979	4717
980	6823
981	7865
982	6070
983	4607
984	4686
985	4293
986	4626
987	4296
988	4055
989	3939
990	2572
991	3108
992	3929
993	2892
994	1968
995	3523
996	4167
997	3598
998	5689
999	8170
1000	7432
1001	5686
1002	4386
1003	3447
1004	3091
1005	3576
1006	5856
1007	6099
1008	4987
1009	4146
1010	4454
1011	4005
1012	2780
1013	1895
1014	2372
1015	3124
1016	3457
1017	3470
1018	2104
1019	2252
1020	3685
1021	5507
1022	6026
1023	5892
1024	5104