1	1029056395
2	112836201
3	33011163
4	14459866
5	7744707
6	4683342
7	3058884
8	2113216
9	1525780
10	1151251
11	890716
12	721998
13	592687
14	510270
15	456908
16	424758
17	410845
18	409581
19	427699
20	469500
21	515274
22	599235
23	722879
24	878350
25	1096274
26	1394786
27	1745032
28	2184975
29	2699767
30	3311182
31	4026916
32	4848890
33	5716917
34	6633191
35	7592778
36	8554355
37	9453826
38	10265355
39	10906717
40	11356604
41	11668822
42	11707495
43	11576242
44	11226332
45	10733868
46	10075044
47	9276927
48	8443130
49	7557372
50	6666217
51	5850848
52	5060023
53	4321564
54	3681787
55	3122850
56	2663130
57	2317370
58	2072182
59	1900545
60	1837020
61	1844489
62	1924412
63	2054998
64	2255414
65	2512575
66	2805232
67	3138551
68	3528736
69	3973215
70	4461093
71	4973989
72	5545316
73	6094664
74	6663043
75	7212612
76	7724969
77	8229881
78	8701517
79	9119053
80	9539415
81	9882671
82	10145779
83	10357520
84	10502583
85	10562854
86	10523796
87	10384880
88	10169702
89	9863448
90	9499944
91	9078169
92	8621695
93	8132499
94	7580973
95	7047533
96	6470918
97	5911134
98	5336663
99	4775408
100	4278352
101	3783857
102	3342435
103	2922749
104	2543303
105	2202336
106	1906475
107	1647722
108	1419938
109	1230997
110	1068196
111	928128
112	806985
113	711071
114	631456
115	570395
116	524844
117	484303
118	456411
119	438613
120	424605
121	413754
122	406726
123	403111
124	404002
125	399011
126	394854
127	388898
128	383390
129	375677
130	371481
131	365482
132	356956
133	352613
134	344204
135	337536
136	328519
137	321573
138	315300
139	305842
140	296811
141	289195
142	279619
143	274041
144	268225
145	262184
146	258582
147	255366
148	252872
149	252493
150	255643
151	257376
152	258685
153	260966
154	265103
155	267956
156	269961
157	273749
158	276992
159	284676
160	290074
161	294011
162	295950
163	300615
164	301565
165	307822
166	312669
167	314349
168	316061
169	314621
170	316031
171	312711
172	311190
173	311791
174	306483
175	303156
176	298894
177	294008
178	287085
179	276010
180	270498
181	261410
182	253770
183	243894
184	238799
185	226023
186	219592
187	211266
188	202783
189	194716
190	190422
191	182609
192	175707
193	168318
194	162508
195	158901
196	153112
197	147512
198	143977
199	139282
200	135527
201	130887
202	127335
203	122599
204	120519
205	119053
206	116531
207	111962
208	111061
209	108562
210	107667
211	106591
212	105258
213	104723
214	103242
215	101281
216	99525
217	98150
218	96929
219	94508
220	93971
221	92892
222	91652
223	90985
224	89077
225	87950
226	86757
227	86284
228	85467
229	83725
230	81729
231	80773
232	81372
233	80250
234	80122
235	78725
236	78895
237	78790
238	77373
239	77769
240	75944
241	76238
242	74975
243	74812
244	74388
245	74955
246	74743
247	74359
248	73512
249	72447
250	72922
251	72191
252	71397
253	72030
254	71147
255	69534
256	69809
257	70138
258	68501
259	69391
260	68048
261	68064
262	67709
263	66511
264	66015
265	65601
266	64288
267	62538
268	62044
269	60596
270	60126
271	58678
272	57472
273	57299
274	56412
275	55926
276	55003
277	53813
278	53257
279	51982
280	51664
281	51105
282	51183
283	50090
284	48822
285	48789
286	48396
287	48134
288	47027
289	46725
290	46548
291	45511
292	45124
293	44796
294	44242
295	43907
296	43690
297	43815
298	43485
299	43291
300	42812
301	41871
302	41701
303	41666
304	40818
305	40523
306	40957
307	39876
308	39856
309	39314
310	39129
311	38722
312	38162
313	38546
314	37420
315	36861
316	36592
317	36524
318	36361
319	36582
320	36643
321	36143
322	36400
323	36010
324	35626
325	35173
326	34975
327	35382
328	35398
329	34126
330	33873
331	34021
332	34050
333	33880
334	34265
335	33630
336	32971
337	32624
338	32853
339	32924
340	32262
341	32608
342	31630
343	31679
344	31476
345	31507
346	31065
347	30782
348	30279
349	29753
350	29435
351	29667
352	29381
353	29460
354	28832
355	28352
356	29093
357	28354
358	27976
359	27802
360	27957
361	26684
362	27134
363	26738
364	26654
365	26873
366	26583
367	26288
368	26166
369	25584
370	25187
371	25060
372	24901
373	25202
374	24909
375	24587
376	24286
377	24828
378	24756
379	24555
380	24042
381	23382
382	23320
383	22850
384	23480
385	22955
386	22560
387	23105
388	22878
389	21939
390	22187
391	22215
392	21800
393	21638
394	21302
395	21854
396	21459
397	21265
398	20931
399	20672
400	20902
401	20875
402	20739
403	20361
404	20544
405	19954
406	20093
407	20325
408	20200
409	19610
410	19655
411	19485
412	19430
413	19450
414	19038
415	18695
416	18686
417	18452
418	18917
419	18611
420	18567
421	18449
422	18478
423	18518
424	18278
425	18415
426	18059
427	17591
428	17889
429	17435
430	18017
431	18076
432	17731
433	17453
434	17218
435	17290
436	16782
437	16894
438	16956
439	16439
440	16590
441	16412
442	16130
443	15999
444	15872
445	16047
446	16058
447	15730
448	15514
449	15567
450	15840
451	15442
452	15385
453	15550
454	14877
455	14825
456	14822
457	14509
458	14499
459	14649
460	14468
461	14654
462	14482
463	14638
464	14394
465	14696
466	14310
467	14170
468	14241
469	13969
470	14269
471	13989
472	13768
473	14042
474	13916
475	13640
476	13565
477	13548
478	13670
479	13379
480	13397
481	13127
482	12912
483	13176
484	13089
485	12948
486	12795
487	12267
488	12631
489	12581
490	12347
491	12566
492	12800
493	12338
494	12142
495	12132
496	12224
497	12079
498	12175
499	12004
500	12043
501	11894
502	11865
503	11885
504	11934
505	11753
506	11513
507	11690
508	11630
509	11630
510	11807
511	11909
512	11737
513	11626
514	11491
515	11481
516	11279
517	11305
518	11532
519	11292
520	10757
521	11041
522	11228
523	10864
524	10988
525	10620
526	10588
527	10445
528	10606
529	10390
530	10592
531	10362
532	10109
533	10106
534	10024
535	9932
536	9982
537	9985
538	9656
539	9886
540	9495
541	9543
542	9651
543	9754
544	9459
545	9425
546	9794
547	9736
548	9590
549	9540
550	9640
551	9506
552	9380
553	9423
554	9476
555	9304
556	9381
557	9367
558	9394
559	9152
560	9079
561	8944
562	9036
563	8975
564	9089
565	8911
566	8879
567	8828
568	8483
569	8824
570	8946
571	8725
572	8689
573	8854
574	8678
575	8729
576	8359
577	8570
578	8400
579	8324
580	8186
581	8109
582	8283
583	8220
584	7919
585	8071
586	7860
587	7914
588	8046
589	8130
590	8028
591	7925
592	8127
593	7934
594	7888
595	7709
596	7763
597	7763
598	7868
599	7950
600	7934
601	7735
602	7603
603	7827
604	7625
605	7796
606	7571
607	7521
608	7609
609	7344
610	7414
611	7247
612	7395
613	7299
614	7265
615	7263
616	7082
617	7179
618	7180
619	7200
620	7095
621	7031
622	6974
623	6932
624	7119
625	6818
626	6950
627	6673
628	6727
629	6774
630	6491
631	6785
632	6705
633	6841
634	6669
635	6721
636	6903
637	6458
638	6563
639	6561
640	6545
641	6572
642	6414
643	6678
644	6572
645	6481
646	6536
647	6671
648	6382
649	6337
650	6272
651	6134
652	6283
653	6364
654	6170
655	6151
656	6320
657	6524
658	6175
659	6152
660	6035
661	5875
662	6134
663	6180
664	6254
665	6043
666	6021
667	5996
668	6158
669	6009
670	5868
671	5940
672	6033
673	5917
674	5920
675	5992
676	6009
677	5767
678	5768
679	5666
680	5605
681	5596
682	5687
683	5690
684	5521
685	5624
686	5630
687	5628
688	5861
689	5698
690	5555
691	5486
692	5458
693	5576
694	5470
695	5530
696	5480
697	5482
698	5584
699	5285
700	5370
701	5572
702	5315
703	5530
704	5494
705	5391
706	5134
707	5255
708	5209
709	5088
710	5165
711	5063
712	5162
713	5273
714	5247
715	5110
716	5112
717	4854
718	5125
719	5054
720	5115
721	5100
722	5176
723	5276
724	4953
725	5097
726	5165
727	5124
728	5142
729	5177
730	5194
731	5164
732	5070
733	4937
734	5103
735	4855
736	4782
737	4859
738	4882
739	4943
740	4898
741	4793
742	4704
743	4761
744	4779
745	4817
746	4908
747	4732
748	4586
749	4674
750	4635
751	4743
752	4751
753	4673
754	4680
755	4508
756	4454
757	4600
758	4430
759	4413
760	4392
761	4455
762	4395
763	4380
764	4297
765	4468
766	4515
767	4420
768	4412
769	4210
770	4353
771	4382
772	4509
773	4515
774	4281
775	4460
776	4315
777	4466
778	4317
779	4279
780	4182
781	4208
782	4260
783	4311
784	4313
785	4313
786	4244
787	4250
788	4129
789	4090
790	4125
791	4182
792	4091
793	3997
794	3923
795	4072
796	4012
797	4159
798	4131
799	4087
800	3916
801	3906
802	4047
803	4024
804	4164
805	4267
806	4105
807	3921
808	3946
809	3990
810	3900
811	3897
812	3886
813	3903
814	3894
815	3861
816	3884
817	4035
818	4046
819	3803
820	3915
821	3749
822	3878
823	3855
824	3867
825	3786
826	3792
827	3603
828	3702
829	3613
830	3704
831	3651
832	3685
833	3636
834	3618
835	3680
836	3647
837	3421
838	3606
839	3583
840	3541
841	3519
842	3692
843	3648
844	3533
845	3475
846	3538
847	3529
848	3490
849	3604
850	3543
851	3532
852	3458
853	3421
854	3543
855	3444
856	3478
857	3327
858	3465
859	3377
860	3458
861	3407
862	3415
863	3484
864	3374
865	3464
866	3364
867	3325
868	3238
869	3496
870	3354
871	3355
872	3334
873	3198
874	3212
875	3364
876	3151
877	3298
878	3194
879	3289
880	3071
881	3188
882	3124
883	3262
884	3217
885	3155
886	3175
887	3179
888	3202
889	3198
890	3064
891	3258
892	3186
893	3232
894	3147
895	3180
896	3102
897	3052
898	3054
899	3015
900	3048
901	3067
902	3093
903	3056
904	3043
905	2969
906	3049
907	3107
908	3061
909	2978
910	2980
911	2885
912	2999
913	3007
914	2992
915	2950
916	2890
917	3033
918	3021
919	3043
920	3078
921	2983
922	2991
923	3057
924	2968
925	2991
926	3068
927	2878
928	2907
929	2897
930	2908
931	2880
932	2952
933	2919
934	2845
935	2871
936	2829
937	2728
938	2814
939	2661
940	2897
941	2758
942	2777
943	2860
944	2919
945	2803
946	2722
947	2762
948	2721
949	2740
950	2671
951	2590
952	2647
953	2630
954	2613
955	2662
956	2711
957	2679
958	2711
959	2674
960	2664
961	2761
962	2733
963	2661
964	2731
965	2684
966	2669
967	2520
968	2616
969	2574
970	2741
971	2722
972	2678
973	2662
974	2633
975	2694
976	2681
977	2459
978	2550
979	2513
980	2568
981	2412
982	2393
983	2399
984	2489
985	2527
986	2436
987	2509
988	2500
989	2446
990	2418
991	2518
992	2489
993	2384
994	2462
995	2461
996	2435
997	2285
998	2391
999	2414
1000	15311726