1	10070
2	9705
3	8842
4	7954
5	7487
6	7996
7	8874
8	9559
9	9712
10	9374
11	8433
12	7673
13	7522
14	7532
15	8059
16	8560
17	8667
18	8657
19	8507
20	8262
21	8488
22	9215
23	11046
24	13185
25	14783
26	14632
27	13335
28	11824
29	9888
30	8506
31	7247
32	5944
33	5750
34	6137
35	7146
36	7792
37	7792
38	7386
39	7186
40	7589
41	8317
42	9496
43	10022
44	10034
45	10243
46	10273
47	9731
48	8738
49	7777
50	7501
51	7629
52	8568
53	8615
54	7946
55	6919
56	6329
57	6241
58	6526
59	7174
60	7846
61	7899
62	7725
63	7946
64	8465
65	9048
66	9403
67	9662
68	9785
69	9653
70	9260
71	8678
72	8392
73	8175
74	8587
75	8789
76	8699
77	9146
78	10080
79	11251
80	11887
81	11691
82	10742
83	9603
84	8790
85	8182
86	7471
87	7267
88	7218
89	7316
90	7476
91	7924
92	8528
93	8806
94	8674
95	8493
96	9022
97	9757
98	9971
99	9710
100	9509
101	9262
102	9068
103	8805
104	9007
105	8479
106	7746
107	6878
108	6862
109	7794
110	9331
111	10032
112	10237
113	10520
114	11220
115	12398
116	12935
117	12662
118	11202
119	10175
120	9770
121	10459
122	10685
123	10175
124	9101
125	8861
126	9415
127	10512
128	11425
129	12065
130	12131
131	11875
132	11020
133	10734
134	10357
135	9912
136	9331
137	9457
138	9466
139	9716
140	9897
141	9750
142	9613
143	10038
144	10381
145	10362
146	9908
147	9830
148	11021
149	12951
150	14810
151	16301
152	16676
153	15369
154	13460
155	12686
156	12207
157	11595
158	10712
159	10354
160	11030
161	11147
162	11098
163	11158
164	11971
165	12667
166	13343
167	14188
168	14846
169	14869
170	14463
171	14277
172	14121
173	14303
174	14328
175	14536
176	14921
177	15176
178	15341
179	15089
180	14186
181	13215
182	12976
183	13611
184	14613
185	15571
186	16272
187	16362
188	15997
189	16444
190	16819
191	17695
192	17371
193	16618
194	15180
195	14063
196	13246
197	13596
198	14409
199	15526
200	15799
201	15618
202	15423
203	15672
204	16011
205	16478
206	17504
207	18336
208	18362
209	17514
210	16445
211	15885
212	15312
213	14936
214	14611
215	14488
216	14376
217	15416
218	16906
219	18510
220	18907
221	19187
222	18950
223	18494
224	16947
225	15920
226	15449
227	15916
228	15797
229	14408
230	13793
231	14457
232	16052
233	16174
234	14317
235	13047
236	13534
237	14530
238	15319
239	16756
240	17741
241	17800
242	16000
243	14217
244	13335
245	13765
246	14517
247	14880
248	14378
249	13728
250	14210
251	14904
252	15917
253	16933
254	18826
255	20352
256	20734
257	20206
258	19580
259	20328
260	20384
261	21185
262	20251
263	18128
264	16681
265	16603
266	17760
267	18083
268	18552
269	18240
270	17479
271	16843
272	17081
273	17622
274	19092
275	19413
276	18844
277	17494
278	17511
279	18660
280	19181
281	18496
282	17352
283	16926
284	17067
285	16846
286	16114
287	15466
288	15816
289	16288
290	15225
291	13769
292	13164
293	13909
294	14678
295	14386
296	15007
297	15486
298	16354
299	16104
300	15400
301	14898
302	14780
303	14587
304	15007
305	16577
306	16944
307	15050
308	12911
309	11846
310	12857
311	14994
312	16725
313	16143
314	13226
315	11276
316	11739
317	12977
318	12903
319	12592
320	13654
321	15199
322	16003
323	15849
324	15422
325	14962
326	15354
327	16148
328	15250
329	13890
330	13012
331	13098
332	13067
333	12240
334	12168
335	13610
336	15156
337	16557
338	16782
339	16312
340	14699
341	14337
342	15580
343	17045
344	16402
345	14723
346	13594
347	14971
348	16288
349	16081
350	15369
351	14609
352	15028
353	17242
354	19697
355	20103
356	18704
357	17223
358	17255
359	17704
360	17860
361	17492
362	17919
363	18539
364	18903
365	18052
366	17531
367	15533
368	13573
369	12504
370	13430
371	15211
372	16428
373	17671
374	18085
375	18145
376	18351
377	18089
378	18102
379	18585
380	19316
381	19625
382	19992
383	19564
384	20434
385	21061
386	20479
387	21133
388	20475
389	17566
390	14279
391	13191
392	12863
393	13564
394	15322
395	16556
396	16101
397	15736
398	15707
399	15459
400	15403
401	16163
402	16991
403	16556
404	16343
405	17725
406	19267
407	20060
408	20940
409	22460
410	24132
411	23035
412	21228
413	19394
414	19020
415	20390
416	21491
417	22038
418	23466
419	24050
420	23317
421	23563
422	23740
423	23818
424	22439
425	20824
426	19467
427	18423
428	19263
429	20207
430	20814
431	20386
432	19429
433	18396
434	18291
435	19386
436	19802
437	20817
438	21382
439	20927
440	20853
441	22614
442	24809
443	23531
444	20600
445	19918
446	20543
447	20548
448	21472
449	20975
450	19966
451	20022
452	21035
453	21505
454	20200
455	18101
456	16569
457	16372
458	18042
459	21313
460	24502
461	25667
462	24820
463	23034
464	21702
465	22013
466	22050
467	21400
468	21980
469	23736
470	23879
471	22879
472	23845
473	25775
474	26660
475	24658
476	21292
477	20176
478	22921
479	26073
480	25533
481	22486
482	21290
483	23306
484	24447
485	23076
486	21953
487	22362
488	22498
489	20401
490	19436
491	21117
492	21305
493	19403
494	17404
495	16688
496	17168
497	19431
498	21744
499	21340
500	21253
501	22093
502	21769
503	19292
504	17370
505	19077
506	21921
507	21143
508	21658
509	23133
510	23328
511	23963
512	24657
513	25098
514	24773
515	24180
516	23209
517	20627
518	19188
519	19943
520	19300
521	16017
522	14175
523	14629
524	16202
525	18714
526	19976
527	19894
528	19722
529	18638
530	16070
531	14209
532	13843
533	14046
534	14322
535	15457
536	16073
537	16880
538	16444
539	14780
540	13819
541	13926
542	14507
543	14617
544	14228
545	14498
546	15410
547	16409
548	16079
549	14239
550	14069
551	14991
552	14691
553	12653
554	11309
555	13255
556	14968
557	13922
558	13250
559	14010
560	12826
561	11442
562	11501
563	13853
564	15579
565	13259
566	11838
567	12657
568	14842
569	16439
570	16279
571	14795
572	13908
573	13760
574	14318
575	14661
576	13398
577	10880
578	9516
579	9828
580	12052
581	14275
582	15023
583	14988
584	15014
585	12533
586	10025
587	10164
588	13089
589	15350
590	16235
591	17564
592	16753
593	13628
594	12150
595	11539
596	10974
597	13283
598	15946
599	15970
600	13423
601	11742
602	12080
603	12234
604	11449
605	11024
606	11612
607	13506
608	15014
609	16679
610	17771
611	17482
612	17171
613	16916
614	16881
615	15831
616	13267
617	12414
618	12536
619	14143
620	17621
621	19207
622	19680
623	17357
624	15329
625	14782
626	13493
627	12222
628	12763
629	12455
630	12263
631	11911
632	11081
633	10982
634	11791
635	11535
636	11092
637	11498
638	10589
639	9672
640	10390
641	12656
642	13059
643	12372
644	14412
645	16309
646	15555
647	15419
648	15415
649	15246
650	16914
651	18395
652	16696
653	15636
654	15715
655	13029
656	11143
657	12632
658	13204
659	11106
660	9485
661	9770
662	10942
663	12453
664	15812
665	17384
666	16631
667	13264
668	10168
669	9567
670	10603
671	11429
672	12654
673	14454
674	13314
675	9940
676	7314
677	6476
678	7586
679	9152
680	10837
681	11780
682	13632
683	18191
684	19856
685	18055
686	16694
687	14541
688	13191
689	11817
690	9488
691	8602
692	10377
693	13427
694	13277
695	13376
696	15315
697	14168
698	12743
699	11518
700	10853
701	13701
702	15943
703	14787
704	13592
705	13978
706	14376
707	14131
708	14989
709	16055
710	13692
711	10536
712	10267
713	14594
714	15589
715	16556
716	18014
717	18463
718	18977
719	17826
720	16707
721	16680
722	20717
723	22192
724	19301
725	14807
726	14978
727	18414
728	19342
729	16856
730	14394
731	16708
732	19603
733	19422
734	19393
735	22059
736	22862
737	21985
738	21271
739	20029
740	20090
741	17583
742	15407
743	16940
744	18930
745	18359
746	17710
747	18009
748	19325
749	21074
750	19892
751	21192
752	21305
753	21678
754	23028
755	22039
756	19277
757	20776
758	19899
759	17603
760	15733
761	17742
762	20638
763	22647
764	22952
765	22284
766	20507
767	20857
768	19674
769	17246
770	18130
771	19559
772	17855
773	17234
774	19306
775	18368
776	19539
777	20851
778	16238
779	12833
780	14846
781	14845
782	14249
783	15995
784	16191
785	15119
786	15546
787	15930
788	15912
789	17934
790	16734
791	15757
792	18162
793	22034
794	22625
795	19023
796	15868
797	14579
798	12875
799	12148
800	13493
801	14704
802	16373
803	16246
804	13669
805	11147
806	10365
807	12615
808	12629
809	11875
810	14015
811	15915
812	16868
813	16580
814	17542
815	15928
816	13562
817	13299
818	14034
819	12900
820	11373
821	8908
822	8754
823	11554
824	11595
825	9893
826	9370
827	9374
828	10074
829	14334
830	15494
831	12739
832	11009
833	13158
834	13959
835	13937
836	14018
837	13487
838	14470
839	13262
840	11085
841	11271
842	10687
843	11220
844	14613
845	14620
846	12853
847	12992
848	12826
849	11901
850	12283
851	12073
852	13909
853	13553
854	11459
855	11063
856	12098
857	15084
858	15471
859	15956
860	14596
861	12747
862	11599
863	9532
864	10809
865	10572
866	7767
867	7089
868	8912
869	9208
870	9753
871	10528
872	9778
873	10279
874	8487
875	8461
876	9142
877	8028
878	6809
879	6915
880	7207
881	7943
882	9499
883	7917
884	6746
885	7530
886	7548
887	6902
888	7403
889	7320
890	5440
891	3989
892	4972
893	5749
894	4764
895	5238
896	6689
897	6637
898	9208
899	8839
900	7962
901	8478
902	8768
903	7306
904	8378
905	7956
906	6273
907	8397
908	9663
909	7794
910	8881
911	10442
912	11488
913	10102
914	9960
915	9832
916	11035
917	13089
918	11584
919	10748
920	12108
921	11786
922	10498
923	9109
924	8648
925	8404
926	9801
927	9587
928	8800
929	7173
930	8164
931	8646
932	9729
933	8429
934	7075
935	9162
936	13082
937	10580
938	7633
939	9262
940	9115
941	7204
942	8061
943	8141
944	8770
945	7071
946	5119
947	5442
948	4771
949	4950
950	4935
951	7053
952	7524
953	7488
954	8755
955	10457
956	10221
957	9355
958	7379
959	6591
960	7381
961	7456
962	8595
963	10606
964	11887
965	11544
966	10689
967	12054
968	9604
969	6169
970	6567
971	10140
972	9640
973	8395
974	6592
975	5983
976	8453
977	7931
978	7620
979	6502
980	6388
981	7164
982	7571
983	8449
984	10093
985	7788
986	4139
987	3788
988	4408
989	7187
990	7360
991	8543
992	6724
993	4473
994	4778
995	6796
996	8204
997	8212
998	6176
999	5849
1000	6254
1001	5212
1002	5543
1003	7236
1004	9432
1005	15799
1006	14364
1007	9514
1008	7675
1009	5312
1010	6812
1011	9346
1012	7899
1013	6695
1014	10402
1015	9696
1016	5958
1017	4056
1018	4255
1019	5010
1020	4851
1021	5430
1022	5908
1023	5137
1024	6788