1	7913
2	7911
3	7895
4	7972
5	8005
6	8215
7	8555
8	8695
9	8820
10	8722
11	8451
12	8524
13	8508
14	8552
15	8425
16	8008
17	7658
18	7654
19	7575
20	7885
21	8315
22	8547
23	8784
24	8942
25	9412
26	9556
27	9404
28	9328
29	8886
30	8931
31	8927
32	9160
33	9214
34	9302
35	9518
36	9266
37	9180
38	9005
39	9261
40	9777
41	10343
42	10587
43	10264
44	10035
45	10205
46	10527
47	10615
48	10555
49	10162
50	10000
51	10283
52	10196
53	10563
54	10503
55	10102
56	9621
57	9706
58	9740
59	10095
60	10485
61	10376
62	10287
63	10215
64	10154
65	10434
66	10580
67	10551
68	10594
69	11057
70	11678
71	12346
72	12408
73	12287
74	12258
75	12358
76	13007
77	13505
78	13899
79	14190
80	14015
81	14003
82	14231
83	14935
84	15355
85	15523
86	15611
87	15994
88	16675
89	17858
90	19210
91	19656
92	19881
93	19964
94	20173
95	20678
96	21854
97	22758
98	24014
99	25819
100	27395
101	28120
102	29099
103	29651
104	30909
105	32565
106	34512
107	36651
108	38639
109	39823
110	41995
111	44204
112	47100
113	49612
114	51757
115	54133
116	56747
117	59109
118	60735
119	61651
120	61325
121	62225
122	61810
123	61075
124	59622
125	58329
126	55736
127	53536
128	51755
129	49916
130	48968
131	47201
132	45125
133	42587
134	39425
135	36802
136	34221
137	32673
138	31788
139	30415
140	29544
141	28074
142	26493
143	24795
144	23601
145	22862
146	21979
147	21572
148	21674
149	21538
150	20488
151	19524
152	18442
153	17726
154	17772
155	17613
156	17340
157	17443
158	17017
159	16421
160	15946
161	15286
162	15187
163	14854
164	15181
165	15338
166	15525
167	15019
168	14907
169	15093
170	14144
171	13928
172	13557
173	13525
174	13639
175	13714
176	13630
177	13151
178	12822
179	12056
180	11642
181	11184
182	10958
183	10835
184	10966
185	11453
186	11928
187	12263
188	12720
189	12839
190	12277
191	11879
192	10985
193	10356
194	9699
195	9676
196	9809
197	10410
198	10403
199	10317
200	10038
201	9855
202	9930
203	10453
204	10887
205	11203
206	11275
207	11463
208	11420
209	11129
210	11165
211	11144
212	11244
213	11071
214	10998
215	10979
216	10930
217	11005
218	10932
219	11299
220	11261
221	11099
222	10974
223	10503
224	10373
225	10251
226	10166
227	9915
228	9871
229	10177
230	10374
231	10596
232	10291
233	10794
234	10428
235	10252
236	9678
237	9541
238	9507
239	9669
240	10015
241	10197
242	10327
243	10825
244	11537
245	12118
246	12362
247	11756
248	11362
249	11430
250	11456
251	11458
252	11188
253	10885
254	10701
255	10429
256	10444
257	10327
258	10376
259	10955
260	11060
261	11171
262	11548
263	11582
264	11891
265	11973
266	11919
267	11168
268	10950
269	11146
270	11165
271	10971
272	11076
273	11045
274	10910
275	11124
276	10877
277	11184
278	11873
279	12727
280	13344
281	13216
282	13072
283	12966
284	13331
285	13175
286	12844
287	12680
288	12741
289	13248
290	13914
291	14672
292	15164
293	15800
294	15783
295	15288
296	14853
297	14623
298	14858
299	15457
300	16486
301	16939
302	17263
303	18157
304	19011
305	19318
306	18863
307	18892
308	19055
309	20019
310	21197
311	22180
312	22776
313	22838
314	22758
315	22976
316	23730
317	24722
318	25147
319	26116
320	26978
321	27464
322	28116
323	28835
324	28662
325	28724
326	28018
327	28857
328	29280
329	29481
330	29390
331	29050
332	28321
333	28022
334	27061
335	26443
336	26312
337	26341
338	26054
339	25646
340	25019
341	25124
342	25095
343	24646
344	24466
345	24746
346	24440
347	24235
348	24279
349	24803
350	25486
351	26196
352	27103
353	27343
354	27070
355	26127
356	25381
357	24333
358	24071
359	23809
360	24326
361	24916
362	24767
363	23388
364	22560
365	22033
366	22023
367	22978
368	22833
369	22304
370	22218
371	22031
372	21241
373	21177
374	21436
375	21920
376	21765
377	21561
378	21218
379	20450
380	19851
381	19641
382	19526
383	20111
384	20594
385	21075
386	21104
387	20777
388	21319
389	22042
390	22333
391	22754
392	22382
393	22189
394	21476
395	21664
396	22636
397	24013
398	25157
399	24451
400	23859
401	24328
402	25051
403	25771
404	26643
405	27820
406	29709
407	30763
408	31700
409	31956
410	32080
411	32819
412	33834
413	34399
414	34688
415	35272
416	36680
417	37673
418	38569
419	40027
420	41263
421	41836
422	41705
423	41079
424	40711
425	40468
426	40671
427	40463
428	39852
429	38273
430	39017
431	39793
432	39003
433	38129
434	38398
435	39846
436	40238
437	39938
438	40237
439	40407
440	39792
441	39567
442	39375
443	39518
444	38924
445	38150
446	39912
447	41390
448	42071
449	41955
450	41956
451	43568
452	44336
453	43456
454	43512
455	43646
456	45058
457	47305
458	50612
459	54054
460	56379
461	57465
462	58658
463	61151
464	64310
465	68090
466	72937
467	74366
468	73920
469	75474
470	75601
471	78214
472	81326
473	86830
474	89486
475	90872
476	92928
477	96102
478	99341
479	101923
480	101424
481	103119
482	106653
483	107615
484	106660
485	106347
486	107180
487	109271
488	110924
489	110374
490	108871
491	109326
492	108994
493	112161
494	112258
495	110410
496	109598
497	109938
498	113038
499	113913
500	117445
501	121474
502	124110
503	126062
504	128324
505	130568
506	134602
507	138646
508	145533
509	150596
510	157060
511	159618
512	160845
513	163276
514	164834
515	169671
516	176331
517	184220
518	192523
519	196756
520	198797
521	200069
522	206775
523	211884
524	218262
525	224168
526	232056
527	243004
528	250824
529	258224
530	266650
531	276452
532	283726
533	290584
534	300023
535	311804
536	322097
537	325665
538	326904
539	328147
540	332231
541	340023
542	342354
543	341832
544	337321
545	329613
546	318636
547	309055
548	300977
549	290183
550	288766
551	286751
552	278722
553	271498
554	267365
555	262072
556	257983
557	257349
558	253629
559	253473
560	256511
561	254691
562	255799
563	256283
564	267126
565	275255
566	280028
567	282374
568	282127
569	281663
570	289577
571	301261
572	312199
573	321951
574	327614
575	338739
576	339811
577	341958
578	343945
579	347989
580	353601
581	352666
582	348999
583	344921
584	337416
585	327194
586	311150
587	300298
588	286814
589	272894
590	258204
591	250135
592	241626
593	228159
594	213355
595	202938
596	194232
597	180713
598	169578
599	160978
600	153311
601	148071
602	142069
603	136052
604	129970
605	125138
606	118947
607	115186
608	110717
609	107486
610	104327
611	100671
612	98924
613	97499
614	92202
615	87704
616	85191
617	83394
618	81010
619	79531
620	78461
621	78162
622	77453
623	76091
624	73852
625	71212
626	70625
627	69997
628	68538
629	67824
630	69416
631	70654
632	70670
633	70594
634	68535
635	66113
636	67117
637	69427
638	69741
639	70206
640	70226
641	71713
642	72941
643	76389
644	75259
645	74336
646	75788
647	76205
648	77581
649	78266
650	78226
651	77755
652	79036
653	78593
654	78782
655	80642
656	79795
657	77276
658	76310
659	76874
660	75531
661	71429
662	69400
663	67529
664	65406
665	62296
666	58205
667	56364
668	55455
669	55882
670	56408
671	55647
672	53875
673	52692
674	53749
675	52964
676	50068
677	47022
678	46371
679	43716
680	41536
681	41357
682	41995
683	42453
684	41712
685	42238
686	41831
687	40449
688	40225
689	40816
690	41675
691	39542
692	37907
693	37432
694	35382
695	35224
696	35508
697	33854
698	31407
699	30623
700	31063
701	31752
702	31219
703	30143
704	30966
705	30887
706	30267
707	28888
708	27865
709	28789
710	29263
711	31161
712	32006
713	29820
714	28363
715	29332
716	30184
717	30847
718	31014
719	31332
720	32952
721	32151
722	30680
723	29965
724	30412
725	30145
726	30087
727	30171
728	31468
729	31673
730	31135
731	30217
732	29030
733	28592
734	27848
735	27483
736	26619
737	26243
738	26868
739	25772
740	23609
741	23128
742	24291
743	23926
744	22750
745	22890
746	23910
747	22202
748	19865
749	18569
750	18903
751	19080
752	18751
753	19027
754	18969
755	18528
756	17773
757	17392
758	16244
759	15718
760	15171
761	15440
762	16238
763	15864
764	14617
765	14385
766	13978
767	13813
768	14404
769	14855
770	14083
771	13466
772	13932
773	13761
774	12757
775	12727
776	12462
777	12525
778	12509
779	13101
780	12625
781	11917
782	12424
783	13074
784	13359
785	12755
786	12959
787	13344
788	12463
789	12568
790	12364
791	12455
792	11950
793	11306
794	11073
795	11572
796	12993
797	13193
798	12271
799	11272
800	10542
801	11501
802	11806
803	10849
804	10709
805	10465
806	10366
807	10623
808	10008
809	10006
810	11097
811	11655
812	11112
813	10098
814	10475
815	10650
816	10942
817	11907
818	11603
819	11281
820	10974
821	11380
822	11946
823	11619
824	10864
825	9769
826	9601
827	10864
828	10736
829	10379
830	10125
831	10924
832	10992
833	10219
834	9553
835	8574
836	8537
837	8949
838	10467
839	10604
840	9964
841	9474
842	9550
843	8740
844	8893
845	8536
846	8583
847	9307
848	9924
849	9834
850	10360
851	11084
852	10981
853	10591
854	10598
855	10435
856	9274
857	9049
858	9545
859	9762
860	10447
861	11322
862	10139
863	8022
864	7180
865	6658
866	7340
867	8260
868	8866
869	9955
870	9686
871	8745
872	8416
873	8477
874	8620
875	8685
876	7938
877	7911
878	8695
879	9349
880	9560
881	9672
882	10498
883	10046
884	9075
885	8179
886	8344
887	8155
888	9056
889	9685
890	10443
891	10249
892	8940
893	8417
894	8191
895	7201
896	7730
897	8018
898	8444
899	9090
900	9163
901	8471
902	7836
903	8327
904	9241
905	9510
906	9052
907	9682
908	9666
909	9354
910	8579
911	8071
912	7721
913	7286
914	8124
915	9198
916	9643
917	9161
918	8613
919	8361
920	7986
921	8363
922	8275
923	8865
924	9287
925	8873
926	8437
927	8898
928	9665
929	10070
930	9867
931	9538
932	9080
933	8808
934	8542
935	8814
936	9050
937	9004
938	8154
939	7615
940	7697
941	7800
942	7589
943	7395
944	8081
945	9193
946	9115
947	8385
948	9002
949	9387
950	8984
951	9478
952	9587
953	8660
954	8420
955	8334
956	8592
957	8459
958	8520
959	8062
960	8199
961	8657
962	7996
963	8121
964	8243
965	8877
966	9009
967	9832
968	9334
969	8361
970	7797
971	8456
972	8942
973	8721
974	7472
975	7905
976	8911
977	8900
978	7802
979	7672
980	7424
981	7453
982	7252
983	7069
984	7224
985	8093
986	8747
987	8583
988	9176
989	9334
990	8413
991	8169
992	8405
993	9384
994	10134
995	10529
996	9057
997	8567
998	8987
999	8555
1000	8389
1001	8938
1002	8674
1003	9259
1004	9368
1005	9501
1006	9385
1007	9470
1008	9629
1009	8446
1010	8067
1011	8377
1012	8915
1013	9637
1014	8395
1015	7800
1016	8301
1017	9022
1018	8243
1019	8848
1020	8901
1021	8420
1022	8238
1023	8271
1024	8403