1	6051
2	5698
3	5707
4	5344
5	4843
6	4390
7	3636
8	4859
9	6361
10	8275
11	9019
12	8181
13	7296
14	6040
15	5415
16	5864
17	5951
18	5850
19	5251
20	5495
21	6356
22	6553
23	6532
24	7285
25	7313
26	7144
27	6526
28	5765
29	5450
30	5360
31	5803
32	5613
33	5926
34	5338
35	5471
36	5588
37	6396
38	7140
39	7721
40	8593
41	7952
42	7323
43	6798
44	6696
45	6847
46	6792
47	6052
48	5958
49	5434
50	4871
51	4754
52	4950
53	5097
54	5511
55	5157
56	5508
57	5328
58	5090
59	5252
60	6062
61	6318
62	6801
63	7438
64	7111
65	7230
66	7010
67	6848
68	6311
69	5617
70	5164
71	6246
72	6519
73	6943
74	6344
75	6235
76	5641
77	5248
78	5357
79	5827
80	6833
81	7214
82	6798
83	6434
84	5473
85	4930
86	6062
87	5987
88	6363
89	6094
90	6757
91	7276
92	7006
93	6396
94	7004
95	7096
96	7522
97	8405
98	8126
99	8187
100	7972
101	7678
102	7402
103	8075
104	7619
105	7065
106	5808
107	5408
108	6258
109	6405
110	7111
111	7360
112	8078
113	8263
114	8036
115	8495
116	7741
117	6768
118	6435
119	6352
120	6241
121	6459
122	6407
123	7154
124	7869
125	8317
126	8377
127	8038
128	7358
129	7276
130	8230
131	8756
132	9025
133	8643
134	7559
135	7038
136	7082
137	7313
138	6740
139	6652
140	6425
141	6398
142	6783
143	6591
144	6603
145	6056
146	6044
147	6438
148	6394
149	5538
150	4948
151	4809
152	4627
153	5583
154	6151
155	6784
156	7725
157	8549
158	8385
159	8117
160	8304
161	8956
162	9056
163	8907
164	8279
165	7380
166	6891
167	6332
168	6990
169	7249
170	7141
171	7061
172	7529
173	7834
174	8641
175	8829
176	9222
177	8927
178	8711
179	8592
180	7811
181	7483
182	7208
183	6917
184	7323
185	7699
186	7744
187	8031
188	7306
189	6615
190	6252
191	6123
192	6281
193	6965
194	7575
195	8352
196	8452
197	9233
198	8977
199	8192
200	6803
201	5133
202	4169
203	4000
204	4313
205	5017
206	5995
207	6919
208	7812
209	8419
210	8292
211	8337
212	8324
213	8037
214	6875
215	6577
216	6281
217	5828
218	5614
219	5604
220	6721
221	8085
222	7955
223	7924
224	7553
225	7960
226	7995
227	7228
228	7402
229	7198
230	7620
231	7566
232	7359
233	6748
234	6266
235	6526
236	7245
237	8013
238	8286
239	6850
240	6848
241	7065
242	7913
243	8169
244	7873
245	8180
246	8370
247	8608
248	9157
249	9455
250	9622
251	8627
252	8351
253	7499
254	6571
255	6511
256	6429
257	6825
258	7126
259	7640
260	8068
261	8333
262	9106
263	10072
264	10353
265	9847
266	8945
267	8144
268	8761
269	8770
270	8783
271	8913
272	8613
273	8867
274	8559
275	8090
276	8292
277	8627
278	10245
279	11301
280	10966
281	9893
282	9638
283	9012
284	8862
285	8418
286	7610
287	7498
288	7641
289	7463
290	7687
291	8156
292	8224
293	8815
294	9252
295	8637
296	8547
297	8566
298	8742
299	8601
300	8820
301	8480
302	8031
303	7722
304	8298
305	9228
306	11063
307	12692
308	12870
309	11162
310	9605
311	8549
312	9304
313	10045
314	10720
315	10732
316	10802
317	10270
318	9970
319	10328
320	9733
321	8906
322	8557
323	8472
324	9247
325	9907
326	9060
327	8564
328	8887
329	10487
330	11935
331	11560
332	10094
333	7596
334	7154
335	8068
336	10329
337	12279
338	13916
339	13949
340	12699
341	12009
342	11143
343	11199
344	10770
345	10327
346	8815
347	7906
348	8342
349	10305
350	12405
351	12988
352	12750
353	11764
354	11659
355	11643
356	11785
357	11199
358	10271
359	9189
360	8455
361	8546
362	8510
363	8717
364	9552
365	11345
366	12751
367	13187
368	10642
369	9267
370	8080
371	8422
372	8634
373	8975
374	9407
375	10350
376	11425
377	12516
378	13573
379	13506
380	11954
381	10675
382	9668
383	10293
384	12243
385	13723
386	14232
387	13714
388	13459
389	12639
390	11703
391	11542
392	11118
393	10940
394	10222
395	11340
396	13482
397	14176
398	14642
399	13322
400	12213
401	11400
402	11280
403	12878
404	14332
405	14226
406	13578
407	13218
408	13091
409	13381
410	14006
411	13228
412	13281
413	13632
414	14533
415	14726
416	15325
417	15438
418	14538
419	13032
420	13226
421	13855
422	13778
423	13579
424	13328
425	12811
426	11896
427	10310
428	9925
429	10605
430	12018
431	12918
432	13156
433	12326
434	10458
435	10502
436	12360
437	15063
438	15191
439	14249
440	14428
441	15254
442	16479
443	16780
444	16541
445	16308
446	15111
447	14287
448	15244
449	15056
450	15412
451	17409
452	18902
453	19363
454	18280
455	17896
456	17288
457	17413
458	18089
459	17496
460	17282
461	17884
462	17738
463	17993
464	18349
465	18562
466	19176
467	20625
468	19920
469	18777
470	17070
471	16848
472	17804
473	19380
474	18976
475	19596
476	20847
477	21926
478	21002
479	21709
480	21604
481	21887
482	21707
483	22244
484	22753
485	23222
486	24126
487	24961
488	24800
489	24547
490	25098
491	23030
492	19578
493	16874
494	15896
495	19238
496	23032
497	25188
498	25467
499	25356
500	25968
501	27339
502	28095
503	28878
504	28371
505	27304
506	27995
507	30785
508	31811
509	31670
510	31290
511	30512
512	31597
513	32365
514	33611
515	33839
516	34576
517	35086
518	35774
519	34840
520	36458
521	37889
522	39577
523	39858
524	38643
525	37606
526	38281
527	42034
528	44404
529	43762
530	43546
531	45642
532	46464
533	47139
534	46567
535	46841
536	46429
537	43345
538	41762
539	43072
540	44775
541	46629
542	48208
543	49665
544	49534
545	49558
546	49017
547	48388
548	47292
549	47140
550	49315
551	52797
552	56567
553	61396
554	63143
555	64768
556	65635
557	68182
558	69411
559	70212
560	70316
561	72254
562	73048
563	70981
564	73399
565	77724
566	82531
567	85963
568	90391
569	93473
570	97464
571	100600
572	102231
573	105071
574	108755
575	114903
576	115483
577	113094
578	119822
579	129407
580	138065
581	142181
582	144182
583	147953
584	156676
585	164738
586	167127
587	171985
588	178448
589	186415
590	198784
591	214574
592	225609
593	230620
594	229474
595	229012
596	233866
597	237194
598	253883
599	284666
600	309410
601	331378
602	354696
603	378656
604	397659
605	412281
606	442701
607	478580
608	510012
609	558638
610	616492
611	675591
612	732151
613	782526
614	837903
615	883885
616	920694
617	987182
618	1046576
619	1103777
620	1152273
621	1198641
622	1237554
623	1266683
624	1275480
625	1275363
626	1293028
627	1308904
628	1353340
629	1389144
630	1442003
631	1473249
632	1495423
633	1531511
634	1556565
635	1550390
636	1522365
637	1475104
638	1412364
639	1337546
640	1253440
641	1211255
642	1184340
643	1171626
644	1140901
645	1128619
646	1140384
647	1172965
648	1235854
649	1275668
650	1340890
651	1407031
652	1460396
653	1532000
654	1601996
655	1672119
656	1703255
657	1743448
658	1755353
659	1711176
660	1638185
661	1550999
662	1471619
663	1346792
664	1207549
665	1078008
666	960976
667	857824
668	776249
669	712957
670	654307
671	606127
672	568744
673	528426
674	489424
675	442466
676	402804
677	367726
678	348447
679	340982
680	323093
681	290406
682	266984
683	258799
684	254480
685	252434
686	236818
687	216836
688	202787
689	196278
690	185390
691	170527
692	161653
693	159285
694	159115
695	157075
696	152307
697	144611
698	135174
699	127071
700	119361
701	109446
702	102813
703	105027
704	104392
705	96388
706	89986
707	87863
708	86034
709	89477
710	91077
711	88771
712	85923
713	82314
714	79195
715	79687
716	79506
717	79135
718	79093
719	76200
720	74327
721	71635
722	70824
723	66160
724	60877
725	57207
726	56913
727	57305
728	59314
729	57397
730	54351
731	53489
732	51174
733	50689
734	47428
735	45055
736	44589
737	44783
738	45974
739	45268
740	43228
741	41768
742	44044
743	47220
744	47001
745	43232
746	41843
747	39625
748	36979
749	34723
750	33202
751	33521
752	34775
753	33710
754	28970
755	31073
756	33984
757	34580
758	32814
759	30763
760	29932
761	29804
762	29323
763	28187
764	26713
765	26551
766	26167
767	26032
768	26458
769	25890
770	25513
771	22698
772	23060
773	24010
774	21634
775	21394
776	23644
777	23570
778	22628
779	21873
780	22312
781	23799
782	26153
783	25020
784	24755
785	25772
786	24336
787	24627
788	25513
789	26624
790	25229
791	22401
792	18723
793	20742
794	22838
795	20299
796	20384
797	20761
798	17636
799	16578
800	16079
801	17427
802	17091
803	16125
804	17912
805	18923
806	16226
807	14594
808	14383
809	15754
810	15153
811	14275
812	14017
813	16775
814	19416
815	17878
816	16116
817	17068
818	17837
819	16813
820	13827
821	13492
822	13578
823	13574
824	16179
825	17328
826	13487
827	14985
828	16646
829	16721
830	15770
831	16562
832	16721
833	14614
834	13355
835	13033
836	12574
837	12954
838	11839
839	11630
840	12752
841	12894
842	11640
843	11071
844	13984
845	14414
846	14580
847	14049
848	15062
849	13882
850	11619
851	11537
852	13094
853	11441
854	10197
855	9729
856	9537
857	11527
858	10669
859	9002
860	8371
861	9190
862	9670
863	11164
864	12621
865	12181
866	9958
867	9015
868	10237
869	11191
870	10107
871	10545
872	11461
873	10739
874	10854
875	11129
876	10506
877	10574
878	11448
879	12159
880	10161
881	9063
882	9919
883	12143
884	12179
885	12027
886	10635
887	9402
888	10006
889	11063
890	11539
891	11496
892	10156
893	9880
894	9969
895	9341
896	9106
897	10504
898	10106
899	8881
900	8509
901	8912
902	11584
903	12784
904	11239
905	13167
906	12357
907	9223
908	9969
909	9232
910	8509
911	7976
912	6960
913	7234
914	9689
915	11125
916	11434
917	10078
918	7592
919	7641
920	9893
921	8366
922	7076
923	8868
924	9764
925	7179
926	6969
927	7824
928	9294
929	8428
930	7338
931	7176
932	7993
933	8301
934	7494
935	8124
936	7762
937	8211
938	8164
939	7861
940	7837
941	7975
942	7548
943	7990
944	7396
945	7189
946	7427
947	8641
948	8605
949	8031
950	8574
951	8256
952	9464
953	10174
954	9688
955	7754
956	6990
957	6732
958	6754
959	6396
960	7187
961	9015
962	8227
963	8128
964	7400
965	7635
966	9024
967	8465
968	6302
969	5139
970	4881
971	5618
972	6524
973	5874
974	5173
975	7151
976	9298
977	7944
978	8067
979	8459
980	7891
981	4306
982	4203
983	6611
984	8199
985	6812
986	5884
987	6654
988	6385
989	5412
990	5226
991	5059
992	6996
993	8996
994	7405
995	7101
996	6866
997	6468
998	5014
999	4322
1000	4346
1001	6934
1002	9497
1003	9643
1004	6877
1005	5651
1006	5686
1007	5626
1008	6843
1009	7259
1010	8546
1011	9207
1012	8863
1013	7292
1014	6392
1015	6625
1016	6464
1017	6214
1018	6834
1019	6556
1020	6466
1021	6251
1022	5779
1023	6387
1024	6877