1	2324390678
2	251086957
3	93982313
4	64405651
5	71456881
6	95249482
7	124507011
8	150569244
9	165473933
10	167421997
11	158212692
12	141948670
13	124260536
14	108805275
15	98193159
16	92773691
17	90887362
18	90750542
19	90352349
20	88168803
21	83810987
22	77430583
23	69302063
24	60054043
25	50676555
26	41989599
27	34283832
28	27699972
29	22399291
30	18371568
31	15259012
32	12936156
33	11264073
34	9989752
35	9028362
36	8327114
37	7751206
38	7301767
39	6891729
40	6553544
41	6231181
42	5925154
43	5608522
44	5351389
45	5053144
46	4771911
47	4527185
48	4290732
49	4056944
50	3840142
51	3626740
52	3423655
53	3243338
54	3084481
55	2939216
56	2803220
57	2675213
58	2560332
59	2447436
60	2348647
61	2252238
62	2170214
63	2088271
64	2014316
65	1939665
66	1865682
67	1801016
68	1738278
69	1680824
70	1626231
71	1575387
72	1521425
73	1475890
74	1426994
75	1385725
76	1340205
77	1307113
78	1268734
79	1234350
80	1205120
81	1169820
82	1138807
83	1113403
84	1084396
85	1054069
86	1033458
87	1006160
88	978592
89	958535
90	934282
91	911456
92	892406
93	869995
94	848106
95	830434
96	814268
97	796410
98	778766
99	760717
100	745826
101	729256
102	713123
103	697627
104	684007
105	671497
106	657701
107	642268
108	630160
109	617368
110	609800
111	596566
112	583200
113	570340
114	560191
115	552794
116	544132
117	531043
118	521632
119	512494
120	502931
121	496876
122	485455
123	479920
124	472085
125	463549
126	453245
127	446085
128	438997
129	432804
130	425970
131	419607
132	411811
133	406449
134	400215
135	393229
136	385054
137	380981
138	379214
139	369596
140	363545
141	359218
142	352510
143	349265
144	345730
145	339968
146	336803
147	330500
148	326082
149	321708
150	317231
151	311994
152	308560
153	304032
154	300023
155	296160
156	293295
157	287642
158	285901
159	281979
160	279109
161	273968
162	271326
163	268723
164	263897
165	259854
166	257339
167	253905
168	252698
169	248316
170	246537
171	242958
172	241102
173	238537
174	235025
175	232644
176	229513
177	228300
178	224670
179	221635
180	219124
181	216680
182	213483
183	211865
184	210327
185	207202
186	205522
187	203458
188	200193
189	198613
190	195968
191	193378
192	192323
193	188759
194	187454
195	185968
196	184102
197	181881
198	179910
199	178582
200	177018
201	173807
202	173365
203	171970
204	169237
205	168108
206	165426
207	164074
208	162251
209	161888
210	159665
211	157565
212	155820
213	154791
214	152830
215	152420
216	150427
217	148542
218	146859
219	145352
220	145068
221	144197
222	141182
223	141262
224	138876
225	137779
226	136583
227	136952
228	135401
229	131977
230	131744
231	130850
232	130026
233	128064
234	127147
235	126485
236	124989
237	123479
238	122413
239	121728
240	120914
241	119751
242	117767
243	116915
244	116261
245	116021
246	114562
247	114417
248	112953
249	111794
250	111696
251	110527
252	109564
253	108971
254	107332
255	106849
256	105920
257	106054
258	104602
259	103371
260	103192
261	102098
262	101067
263	100933
264	99422
265	98677
266	98148
267	96783
268	97288
269	95737
270	95085
271	94192
272	93722
273	93527
274	91557
275	91667
276	91469
277	90001
278	89275
279	89215
280	89239
281	87172
282	87971
283	87135
284	85698
285	85086
286	84643
287	83479
288	83137
289	82271
290	82190
291	82103
292	81380
293	81272
294	80896
295	79592
296	78978
297	78521
298	77854
299	77401
300	76556
301	76236
302	76161
303	75177
304	74792
305	74028
306	73084
307	73156
308	72585
309	71603
310	70996
311	70597
312	70221
313	69790
314	69735
315	69128
316	68037
317	68252
318	67772
319	66972
320	66888
321	65733
322	65665
323	65277
324	64989
325	63990
326	63678
327	63285
328	63291
329	62630
330	62289
331	62158
332	60970
333	61302
334	61489
335	60440
336	60109
337	59176
338	58717
339	58698
340	58336
341	58219
342	57292
343	57261
344	56131
345	56097
346	56300
347	55851
348	55488
349	55134
350	54949
351	54546
352	54561
353	53488
354	52819
355	52552
356	52955
357	51859
358	52062
359	51585
360	51478
361	51306
362	50273
363	50581
364	50170
365	49378
366	49598
367	48604
368	48859
369	47992
370	47958
371	47702
372	47593
373	47713
374	47785
375	46768
376	46814
377	46266
378	45974
379	45413
380	45360
381	45407
382	45130
383	45155
384	44125
385	44064
386	44362
387	43424
388	42992
389	42877
390	43410
391	43094
392	42710
393	42818
394	42352
395	42475
396	42028
397	41995
398	41216
399	40877
400	40841
401	40237
402	40552
403	39937
404	39998
405	39950
406	39877
407	39390
408	39280
409	39238
410	38563
411	38674
412	38280
413	38399
414	37897
415	37854
416	37602
417	37704
418	37602
419	37139
420	37249
421	36744
422	37044
423	36555
424	36487
425	36488
426	36250
427	35999
428	35720
429	35208
430	34659
431	35017
432	34772
433	34542
434	33988
435	34081
436	33781
437	33804
438	34309
439	33734
440	33458
441	33219
442	33138
443	33385
444	32730
445	32818
446	32260
447	32371
448	32362
449	32031
450	31896
451	31650
452	31724
453	31490
454	30299
455	31039
456	31392
457	30643
458	30811
459	30701
460	30917
461	30321
462	29970
463	29664
464	29867
465	29500
466	29672
467	29864
468	29486
469	29354
470	29109
471	29298
472	29057
473	28867
474	28636
475	28362
476	27841
477	28248
478	28157
479	27958
480	27743
481	27605
482	27512
483	27446
484	27397
485	27599
486	27220
487	27234
488	26812
489	26715
490	26187
491	26435
492	26282
493	26218
494	26378
495	26322
496	25799
497	25644
498	25578
499	25527
500	25556
501	25367
502	25540
503	25222
504	25161
505	24973
506	24669
507	25192
508	24906
509	24504
510	24624
511	24652
512	24414
513	24403
514	24406
515	24137
516	23993
517	23834
518	23680
519	23641
520	23617
521	23234
522	23539
523	23144
524	22883
525	22972
526	22863
527	22493
528	22735
529	22948
530	22472
531	22654
532	22371
533	22251
534	22420
535	22264
536	22311
537	21962
538	22444
539	21708
540	21854
541	21587
542	21569
543	21887
544	21524
545	21496
546	21127
547	21374
548	21542
549	20675
550	20977
551	20956
552	20951
553	21068
554	20777
555	20817
556	20618
557	20388
558	20609
559	20442
560	20589
561	20566
562	20160
563	20002
564	19757
565	19847
566	19628
567	20041
568	20083
569	19653
570	19840
571	19717
572	19388
573	19547
574	19830
575	19401
576	19435
577	19280
578	19621
579	19969
580	19515
581	18963
582	19048
583	19302
584	19423
585	19009
586	18942
587	18762
588	19274
589	19054
590	19087
591	19099
592	18960
593	18918
594	18907
595	18971
596	18785
597	18602
598	18607
599	18542
600	18675
601	18517
602	18435
603	18262
604	18288
605	18181
606	18362
607	18362
608	18178
609	18279
610	18025
611	17700
612	17937
613	17963
614	17880
615	17992
616	17877
617	17833
618	17816
619	17782
620	17680
621	17588
622	17760
623	17533
624	17662
625	17772
626	17461
627	17589
628	17367
629	17524
630	17604
631	17781
632	17648
633	17436
634	17471
635	17351
636	17440
637	17600
638	17421
639	17550
640	17645
641	17073
642	17466
643	17132
644	17510
645	17269
646	17216
647	17176
648	17362
649	17153
650	17185
651	16638
652	16634
653	16651
654	17083
655	16868
656	17022
657	17224
658	16735
659	16804
660	16399
661	16364
662	16427
663	16503
664	16381
665	16083
666	16350
667	15997
668	16067
669	15957
670	15571
671	15648
672	15508
673	15116
674	15129
675	15263
676	15162
677	15043
678	14765
679	14962
680	14714
681	14824
682	14825
683	14516
684	14588
685	14785
686	14672
687	14494
688	14394
689	14540
690	14356
691	14311
692	14307
693	14142
694	14087
695	14181
696	14068
697	14195
698	13958
699	14177
700	14095
701	13864
702	13787
703	13642
704	13460
705	13380
706	13562
707	13430
708	13606
709	13532
710	13622
711	13469
712	13599
713	13457
714	13296
715	13379
716	13082
717	13146
718	13197
719	13150
720	13177
721	13296
722	12985
723	13062
724	12868
725	12928
726	13172
727	12875
728	13098
729	12782
730	12891
731	12936
732	12773
733	12946
734	12822
735	12832
736	12741
737	12652
738	12731
739	12772
740	12758
741	12589
742	12477
743	12547
744	12458
745	12509
746	12521
747	12489
748	12482
749	12299
750	12371
751	12531
752	12421
753	12395
754	12320
755	12042
756	12356
757	12109
758	11862
759	12045
760	11680
761	11981
762	11945
763	11869
764	11858
765	11732
766	11836
767	11737
768	11521
769	11701
770	11379
771	11439
772	11579
773	11367
774	11432
775	11391
776	11402
777	11172
778	11463
779	11407
780	11424
781	11400
782	11062
783	11081
784	11271
785	11203
786	11186
787	10946
788	11206
789	10945
790	11041
791	11038
792	10988
793	11076
794	11108
795	10882
796	11018
797	10727
798	10726
799	10819
800	10719
801	10636
802	10697
803	10710
804	10535
805	10527
806	10510
807	10638
808	10499
809	10749
810	10705
811	10654
812	10424
813	10403
814	10617
815	10567
816	10374
817	10200
818	10251
819	10266
820	10208
821	10319
822	10159
823	10232
824	10182
825	10398
826	10066
827	9772
828	9873
829	9836
830	9958
831	9959
832	9862
833	10001
834	9844
835	9774
836	9764
837	9911
838	9753
839	9638
840	9805
841	9484
842	9555
843	9611
844	9494
845	9542
846	9388
847	9465
848	9451
849	9407
850	9331
851	9421
852	9403
853	9022
854	9245
855	9067
856	9173
857	8902
858	9018
859	9061
860	8929
861	8742
862	8838
863	8789
864	8700
865	8581
866	8745
867	8632
868	8623
869	8708
870	8533
871	8593
872	8466
873	8439
874	8373
875	8266
876	8489
877	8376
878	8310
879	8440
880	8385
881	8029
882	8148
883	7971
884	8108
885	8027
886	8038
887	8034
888	7954
889	7884
890	7958
891	7999
892	8011
893	7968
894	7898
895	7795
896	7823
897	8002
898	7831
899	7681
900	7690
901	7715
902	7775
903	7538
904	7874
905	7760
906	7725
907	7690
908	7598
909	7777
910	7751
911	7787
912	7574
913	7671
914	7584
915	7542
916	7490
917	7448
918	7543
919	7326
920	7726
921	7327
922	7477
923	7426
924	7471
925	7467
926	7541
927	7473
928	7117
929	7285
930	7403
931	7352
932	7399
933	7360
934	7247
935	7290
936	6969
937	7051
938	7106
939	7285
940	7228
941	6984
942	7179
943	7022
944	7024
945	7131
946	7172
947	7172
948	6849
949	7078
950	6906
951	6911
952	7032
953	6989
954	7055
955	6831
956	6978
957	6852
958	6708
959	6866
960	6858
961	6808
962	6870
963	6829
964	6852
965	6855
966	6913
967	6801
968	6622
969	6593
970	6661
971	6725
972	6677
973	6549
974	6661
975	6568
976	6627
977	6644
978	6485
979	6478
980	6557
981	6482
982	6319
983	6172
984	6445
985	6290
986	6311
987	6111
988	6309
989	6221
990	6232
991	6083
992	6112
993	6192
994	6130
995	6033
996	6076
997	6162
998	6202
999	6016
1000	24771290