1	550980631
2	83033810
3	41691197
4	31788953
5	28871889
6	26842876
7	24985713
8	22478531
9	19518744
10	16471434
11	13931462
12	11323849
13	9081368
14	7433047
15	6152984
16	5313289
17	4745666
18	4324299
19	3999251
20	3809937
21	3813185
22	3823033
23	3822960
24	3783933
25	3752089
26	3706446
27	3649093
28	3607790
29	3568041
30	3501818
31	3459997
32	3450423
33	3424766
34	3339541
35	3252519
36	3178318
37	3121753
38	3049590
39	2947627
40	2868738
41	2802761
42	2730225
43	2621908
44	2491249
45	2375373
46	2277337
47	2158799
48	2043204
49	1923481
50	1811498
51	1701164
52	1605966
53	1509369
54	1428557
55	1349487
56	1276637
57	1232458
58	1191371
59	1159990
60	1129317
61	1101690
62	1077570
63	1055037
64	1035674
65	1010305
66	1008005
67	986187
68	966702
69	950413
70	932539
71	913294
72	896289
73	874215
74	842283
75	818416
76	786917
77	761925
78	734665
79	701729
80	669152
81	624714
82	589803
83	562135
84	529303
85	499625
86	472575
87	446963
88	429732
89	409590
90	390864
91	378036
92	361357
93	344938
94	338678
95	326327
96	318499
97	312718
98	296802
99	291133
100	288421
101	288179
102	284508
103	273537
104	266214
105	262530
106	258734
107	250295
108	239539
109	234907
110	226491
111	221232
112	212842
113	206630
114	201960
115	198530
116	199378
117	204723
118	211270
119	216365
120	217124
121	220445
122	220985
123	218423
124	218063
125	216260
126	216991
127	221448
128	223199
129	226612
130	231774
131	235045
132	239264
133	240349
134	242889
135	244426
136	247264
137	250940
138	254370
139	252610
140	252673
141	250729
142	244787
143	237403
144	235105
145	234004
146	233178
147	235717
148	236817
149	234725
150	233531
151	230234
152	230081
153	230256
154	229673
155	233744
156	231687
157	235517
158	236071
159	239360
160	237968
161	237265
162	234386
163	231240
164	229354
165	227744
166	230875
167	231789
168	233987
169	233943
170	232432
171	236837
172	236662
173	233175
174	236357
175	237211
176	238548
177	239764
178	241168
179	240345
180	245393
181	250918
182	251381
183	254126
184	249990
185	250042
186	247394
187	248287
188	249502
189	249911
190	249402
191	250716
192	253419
193	250830
194	250885
195	251702
196	255501
197	260288
198	260400
199	261721
200	263253
201	265311
202	270448
203	274695
204	275914
205	278408
206	282460
207	283804
208	289493
209	294615
210	298915
211	300409
212	304617
213	310174
214	310632
215	314907
216	315441
217	319483
218	313593
219	311215
220	307745
221	311018
222	311217
223	311137
224	315057
225	316320
226	316810
227	320243
228	319152
229	319332
230	316230
231	311892
232	312479
233	305174
234	304336
235	305438
236	300407
237	296457
238	294411
239	290330
240	285863
241	279382
242	273319
243	267319
244	261481
245	257240
246	250995
247	250038
248	246718
249	244507
250	238331
251	235501
252	230790
253	226901
254	220093
255	213866
256	209064
257	206775
258	201846
259	198300
260	194178
261	189264
262	186581
263	185522
264	183737
265	179080
266	175222
267	173153
268	173912
269	169109
270	165477
271	161304
272	158454
273	157482
274	156201
275	151619
276	149515
277	145280
278	143059
279	142536
280	141087
281	137677
282	137241
283	136244
284	133698
285	132356
286	132841
287	131402
288	131382
289	130943
290	130686
291	129757
292	128395
293	128966
294	126943
295	125026
296	124090
297	123027
298	121059
299	120008
300	118623
301	117591
302	117688
303	113055
304	111025
305	109469
306	108171
307	107559
308	105815
309	106893
310	107131
311	108391
312	107095
313	107182
314	107025
315	107052
316	107430
317	107779
318	108643
319	107988
320	109006
321	109900
322	111675
323	111730
324	111864
325	113183
326	111811
327	113679
328	112326
329	113297
330	111783
331	112772
332	114454
333	116514
334	117302
335	119747
336	121278
337	121828
338	123860
339	127339
340	127185
341	128732
342	130808
343	132170
344	133164
345	134619
346	135415
347	136364
348	138802
349	139661
350	140205
351	139526
352	143127
353	143273
354	143847
355	147885
356	150955
357	152059
358	154862
359	155945
360	157072
361	158238
362	157656
363	160571
364	162730
365	162790
366	165298
367	169785
368	171869
369	171916
370	170112
371	172342
372	173407
373	174118
374	175214
375	175181
376	178717
377	176214
378	177325
379	176620
380	178663
381	177595
382	179625
383	179300
384	180092
385	177827
386	179310
387	179698
388	181778
389	181948
390	181448
391	182263
392	181445
393	181479
394	181601
395	182297
396	180443
397	180026
398	178251
399	174696
400	173748
401	171182
402	168769
403	166919
404	165755
405	161707
406	161442
407	159534
408	159037
409	156067
410	153169
411	150741
412	149449
413	148508
414	147262
415	145776
416	144642
417	144135
418	142835
419	142309
420	142475
421	139269
422	138295
423	136489
424	134685
425	132983
426	128993
427	127243
428	124098
429	121882
430	119736
431	116382
432	114299
433	109968
434	107901
435	105139
436	104054
437	101498
438	97835
439	96449
440	95564
441	91351
442	89150
443	86329
444	84824
445	83223
446	81860
447	79969
448	77770
449	75376
450	73962
451	72014
452	71819
453	69465
454	68110
455	66254
456	66798
457	65697
458	64214
459	62761
460	61813
461	61826
462	59831
463	58908
464	57857
465	56311
466	55077
467	54876
468	54415
469	53452
470	52782
471	52423
472	52622
473	52280
474	51433
475	50791
476	51439
477	51935
478	50988
479	49915
480	49015
481	47859
482	47490
483	47977
484	47869
485	48276
486	46696
487	46680
488	45970
489	46407
490	45800
491	45477
492	45705
493	45243
494	44521
495	44837
496	45075
497	44982
498	44957
499	45292
500	45790
501	45934
502	46696
503	46160
504	46415
505	45933
506	45665
507	45549
508	46030
509	46035
510	46314
511	47224
512	47418
513	45920
514	46040
515	46442
516	45513
517	45998
518	45159
519	43831
520	43809
521	44205
522	43774
523	43517
524	43133
525	42538
526	43395
527	43072
528	42776
529	41996
530	41674
531	41495
532	40907
533	40837
534	42146
535	42400
536	42989
537	43073
538	42227
539	42589
540	43421
541	42804
542	42554
543	42996
544	43616
545	44244
546	43910
547	44163
548	45033
549	44350
550	43912
551	43476
552	43184
553	43103
554	42753
555	43489
556	42876
557	42182
558	42332
559	42342
560	41553
561	41662
562	40907
563	41252
564	40453
565	40326
566	40373
567	41167
568	41256
569	41721
570	41612
571	42051
572	42681
573	43277
574	42866
575	42044
576	41919
577	42599
578	42319
579	43086
580	42583
581	43841
582	43512
583	44581
584	45187
585	44259
586	45404
587	45812
588	46419
589	46359
590	46552
591	46836
592	46128
593	47139
594	46369
595	47757
596	48002
597	47992
598	48265
599	48113
600	47855
601	47571
602	47446
603	47728
604	46910
605	47762
606	47246
607	47567
608	46705
609	46103
610	44992
611	44755
612	44635
613	45123
614	45720
615	46488
616	46981
617	47039
618	47404
619	48110
620	47489
621	47614
622	48878
623	49431
624	50195
625	50580
626	50338
627	50791
628	51556
629	51958
630	51115
631	49534
632	50139
633	51122
634	50908
635	51244
636	50470
637	51488
638	51553
639	52318
640	52675
641	52602
642	52594
643	52617
644	52238
645	52378
646	52814
647	52465
648	53022
649	51398
650	51686
651	51617
652	50377
653	50023
654	50000
655	49255
656	49226
657	48604
658	48440
659	48382
660	48811
661	48912
662	48066
663	47405
664	47399
665	47274
666	46972
667	46744
668	46166
669	44977
670	44579
671	44764
672	44754
673	43494
674	42491
675	42047
676	42070
677	41319
678	42014
679	41424
680	40810
681	40133
682	38851
683	39888
684	39960
685	38677
686	39089
687	38465
688	38576
689	37957
690	37874
691	37705
692	37477
693	37606
694	36988
695	37467
696	37331
697	36856
698	36813
699	36752
700	36712
701	36199
702	36137
703	36029
704	35859
705	35486
706	35429
707	34877
708	34561
709	33883
710	33980
711	33162
712	32115
713	31985
714	32170
715	31733
716	31244
717	30383
718	30482
719	30869
720	29808
721	29422
722	29153
723	28553
724	27430
725	27596
726	27387
727	26736
728	27166
729	26749
730	26419
731	25937
732	25760
733	25231
734	25250
735	24607
736	24359
737	23688
738	23465
739	22835
740	22600
741	22482
742	21473
743	20962
744	20316
745	20151
746	19517
747	19355
748	19244
749	18456
750	18137
751	18143
752	17457
753	17252
754	16787
755	16934
756	16735
757	16130
758	16183
759	15972
760	15345
761	15402
762	14737
763	14558
764	13956
765	13584
766	13269
767	13048
768	12818
769	12673
770	12703
771	12688
772	12020
773	11529
774	11730
775	11625
776	11961
777	11894
778	11644
779	11530
780	11698
781	11787
782	11364
783	11364
784	11004
785	10759
786	10299
787	10482
788	10098
789	10107
790	9453
791	9494
792	9426
793	9150
794	9229
795	9137
796	8505
797	8424
798	8373
799	8206
800	7867
801	7580
802	7327
803	6932
804	6628
805	6250
806	5864
807	5799
808	5412
809	5469
810	5105
811	5043
812	4995
813	4892
814	4682
815	4633
816	4489
817	4469
818	4546
819	4488
820	4560
821	4452
822	4380
823	4288
824	4239
825	4291
826	4392
827	4469
828	4778
829	4661
830	4720
831	4593
832	4955
833	4806
834	4774
835	4808
836	4638
837	4530
838	4565
839	4781
840	4804
841	4838
842	4717
843	4804
844	4837
845	4773
846	4768
847	4804
848	4734
849	4641
850	4485
851	4448
852	4365
853	4297
854	4352
855	4210
856	4124
857	3890
858	4112
859	3902
860	3827
861	3876
862	3920
863	3752
864	3633
865	3569
866	3620
867	3672
868	3576
869	3529
870	3641
871	3789
872	3811
873	3807
874	3897
875	3833
876	3689
877	3821
878	4135
879	3867
880	4102
881	4152
882	4145
883	4261
884	4133
885	4115
886	4177
887	4130
888	4306
889	4218
890	4383
891	4391
892	4369
893	4335
894	4665
895	4870
896	4868
897	4904
898	4802
899	5047
900	4897
901	4737
902	4847
903	4697
904	4687
905	4797
906	4741
907	4809
908	4868
909	5082
910	5157
911	5144
912	5170
913	5176
914	5109
915	5188
916	5182
917	5261
918	5401
919	5408
920	5497
921	5637
922	5642
923	5757
924	5557
925	5861
926	5908
927	5975
928	6032
929	5801
930	6249
931	6270
932	6456
933	6892
934	7031
935	7323
936	7436
937	7465
938	7690
939	7762
940	7860
941	8159
942	8224
943	8150
944	8411
945	8377
946	8295
947	8259
948	8428
949	8534
950	8686
951	8646
952	8575
953	8459
954	8446
955	8308
956	8486
957	8563
958	8559
959	8661
960	8416
961	8505
962	8621
963	8715
964	8429
965	8532
966	8634
967	8300
968	8247
969	8497
970	8705
971	8782
972	8391
973	8494
974	8615
975	8743
976	8724
977	8717
978	8899
979	9122
980	9209
981	9131
982	9297
983	9515
984	9471
985	9850
986	9891
987	9742
988	9849
989	10128
990	10107
991	10578
992	10557
993	10835
994	11007
995	10834
996	11411
997	11292
998	11526
999	11338
1000	7463710