1	2879122779
2	198953667
3	42287668
4	17283779
5	11403647
6	10236730
7	11048139
8	13000565
9	15777605
10	19086576
11	22758257
12	26390084
13	30031353
14	33500718
15	36693157
16	39678403
17	42531122
18	45678010
19	49162495
20	53407090
21	58489069
22	64218854
23	70191170
24	76527927
25	82858059
26	88706460
27	93880999
28	98088593
29	100981195
30	102429864
31	102190591
32	100327832
33	97008802
34	92128350
35	86015641
36	79102423
37	71497390
38	63615764
39	55640816
40	47720851
41	40300859
42	33544287
43	27623126
44	22432118
45	18032090
46	14265704
47	11173431
48	8683257
49	6694940
50	5195098
51	4050421
52	3210936
53	2576403
54	2103090
55	1772896
56	1546074
57	1390710
58	1284232
59	1211055
60	1153488
61	1116073
62	1088310
63	1057497
64	1034003
65	1013214
66	990500
67	966549
68	944614
69	918626
70	889526
71	850541
72	813994
73	781101
74	744804
75	704913
76	668686
77	633186
78	600559
79	570542
80	538715
81	512288
82	487627
83	467031
84	445711
85	425497
86	412250
87	398063
88	381748
89	372244
90	360353
91	351183
92	344062
93	339391
94	333179
95	326552
96	320722
97	313378
98	309630
99	302739
100	300036
101	292638
102	285451
103	279570
104	276007
105	268353
106	263182
107	257936
108	251821
109	248373
110	240868
111	236072
112	230295
113	227302
114	220905
115	216024
116	211337
117	206668
118	201629
119	198397
120	193478
121	186758
122	183889
123	180418
124	176833
125	172771
126	169016
127	165207
128	163556
129	158447
130	154349
131	151427
132	148943
133	144988
134	142338
135	141123
136	137785
137	134599
138	133666
139	130474
140	128639
141	127221
142	125800
143	124127
144	122352
145	120691
146	118727
147	116675
148	115966
149	113802
150	111877
151	110442
152	107140
153	105975
154	104569
155	102511
156	101219
157	100158
158	97453
159	96365
160	94162
161	94449
162	92297
163	91300
164	89871
165	88997
166	86501
167	85539
168	84359
169	82544
170	82224
171	81169
172	79437
173	78458
174	78442
175	76728
176	75570
177	74149
178	73751
179	72223
180	70788
181	71296
182	69343
183	68241
184	68554
185	66751
186	66669
187	66440
188	65211
189	64462
190	64171
191	63939
192	63365
193	62490
194	60695
195	61238
196	60350
197	59686
198	59131
199	58800
200	57592
201	57736
202	56824
203	55752
204	55646
205	54827
206	54588
207	53536
208	53172
209	52740
210	52635
211	51478
212	51371
213	50951
214	48910
215	49253
216	48576
217	47836
218	47940
219	46890
220	46980
221	45792
222	45819
223	45048
224	44952
225	44659
226	44764
227	44148
228	43501
229	43581
230	43233
231	42684
232	42992
233	41994
234	41549
235	41496
236	41045
237	40513
238	40707
239	40352
240	40267
241	39646
242	39047
243	38734
244	37959
245	38141
246	37804
247	37369
248	37281
249	36640
250	36432
251	35927
252	35449
253	35708
254	34997
255	34362
256	34604
257	33631
258	34357
259	33143
260	33052
261	33936
262	33397
263	32721
264	32456
265	31523
266	31521
267	32018
268	31668
269	31147
270	30827
271	30763
272	30940
273	29533
274	29391
275	29554
276	29766
277	29401
278	29075
279	28350
280	28102
281	28498
282	28479
283	27958
284	28323
285	27905
286	27755
287	27072
288	26998
289	27185
290	26496
291	26710
292	26615
293	26386
294	26016
295	25542
296	25781
297	25772
298	25154
299	25324
300	24780
301	24607
302	24265
303	24361
304	24254
305	24264
306	24029
307	24065
308	24366
309	23780
310	23575
311	23239
312	23224
313	23315
314	22978
315	22876
316	22544
317	22855
318	22612
319	22069
320	22428
321	22060
322	21641
323	21756
324	21943
325	21747
326	22181
327	21626
328	21777
329	21386
330	20965
331	21108
332	21467
333	20965
334	20494
335	20729
336	20360
337	20453
338	20221
339	20022
340	19606
341	19372
342	19223
343	19381
344	19970
345	19488
346	19398
347	19016
348	19251
349	18958
350	18822
351	19118
352	18957
353	18637
354	18326
355	18203
356	18402
357	18544
358	18073
359	18030
360	18237
361	18138
362	18050
363	17986
364	17726
365	17954
366	17690
367	17664
368	17474
369	17760
370	17336
371	17137
372	17075
373	16927
374	16741
375	16412
376	16510
377	16548
378	16641
379	16159
380	16488
381	16268
382	16191
383	16088
384	15882
385	15761
386	15901
387	16067
388	15986
389	16029
390	16013
391	15280
392	15328
393	14997
394	15422
395	15094
396	14949
397	14970
398	14959
399	15029
400	14773
401	14931
402	14617
403	14853
404	14479
405	14427
406	14414
407	14253
408	14303
409	14015
410	13587
411	13975
412	13942
413	13849
414	13455
415	13626
416	13564
417	13788
418	13223
419	13631
420	13285
421	13179
422	13139
423	13158
424	13305
425	13044
426	13137
427	13025
428	13006
429	12798
430	12700
431	12941
432	12817
433	12713
434	12477
435	12611
436	12398
437	12495
438	12565
439	12443
440	12320
441	12028
442	12043
443	12102
444	11950
445	12075
446	11735
447	11884
448	11620
449	12003
450	11749
451	11612
452	11760
453	11404
454	11308
455	11221
456	11358
457	11376
458	11263
459	11473
460	11298
461	11275
462	11106
463	11028
464	10870
465	10917
466	11026
467	10787
468	10976
469	10693
470	10429
471	10724
472	10329
473	10399
474	10222
475	10295
476	10262
477	10058
478	10236
479	10083
480	10054
481	9951
482	9925
483	9885
484	10101
485	9809
486	10033
487	9907
488	10048
489	9803
490	9874
491	9859
492	9852
493	9897
494	9647
495	9513
496	9470
497	9562
498	9421
499	9601
500	9598
501	9789
502	9527
503	9313
504	9594
505	9250
506	9301
507	9039
508	9132
509	8849
510	8787
511	8787
512	8897
513	8840
514	8853
515	9015
516	9154
517	8569
518	8619
519	8483
520	8590
521	8562
522	8510
523	8349
524	8407
525	8373
526	8432
527	8572
528	8264
529	8183
530	8307
531	8352
532	8164
533	8128
534	8100
535	7958
536	8089
537	8019
538	7935
539	7844
540	8011
541	7787
542	7771
543	7718
544	7641
545	7884
546	7542
547	7641
548	7545
549	7576
550	7651
551	7579
552	7535
553	7495
554	7511
555	7446
556	7627
557	7439
558	7475
559	7364
560	7327
561	7387
562	7406
563	7337
564	7319
565	7345
566	7213
567	7265
568	7160
569	7106
570	7187
571	6863
572	6908
573	6940
574	7069
575	7029
576	6891
577	6602
578	6883
579	6602
580	6939
581	6773
582	6652
583	6764
584	6696
585	6629
586	6695
587	6515
588	6726
589	6588
590	6592
591	6347
592	6624
593	6614
594	6616
595	6572
596	6598
597	6317
598	6486
599	6576
600	6405
601	6339
602	6370
603	6270
604	6393
605	6190
606	6048
607	6221
608	6442
609	6208
610	6142
611	6143
612	6170
613	6025
614	6133
615	6217
616	6070
617	5968
618	6098
619	6067
620	6013
621	5766
622	6037
623	6073
624	5870
625	5890
626	5924
627	5954
628	5959
629	5929
630	5831
631	5703
632	5853
633	5821
634	5708
635	5552
636	5696
637	5698
638	5830
639	5691
640	5712
641	5723
642	5617
643	5570
644	5627
645	5443
646	5386
647	5529
648	5388
649	5635
650	5599
651	5616
652	5536
653	5516
654	5608
655	5420
656	5439
657	5598
658	5451
659	5436
660	5440
661	5391
662	5405
663	5163
664	5044
665	5227
666	5163
667	5247
668	5101
669	5308
670	5200
671	5202
672	5192
673	4998
674	5179
675	5121
676	5087
677	5039
678	5166
679	5108
680	5207
681	5128
682	4991
683	5039
684	5031
685	5035
686	4907
687	4841
688	4726
689	4884
690	4838
691	4762
692	4782
693	4735
694	4726
695	4743
696	4846
697	4756
698	4778
699	4759
700	4652
701	4807
702	4759
703	4785
704	4729
705	4797
706	4774
707	4617
708	4621
709	4459
710	4631
711	4629
712	4456
713	4625
714	4568
715	4623
716	4422
717	4618
718	4434
719	4519
720	4224
721	4344
722	4322
723	4320
724	4312
725	4376
726	4449
727	4463
728	4345
729	4235
730	4366
731	4438
732	4364
733	4327
734	4247
735	4332
736	4350
737	4427
738	4324
739	4264
740	4270
741	4383
742	4498
743	4274
744	4355
745	4339
746	4298
747	4315
748	4353
749	4082
750	4158
751	4215
752	4119
753	4183
754	4138
755	4089
756	4102
757	4101
758	4075
759	4045
760	3958
761	4056
762	3982
763	4039
764	4054
765	3993
766	3909
767	3817
768	4033
769	3849
770	3914
771	3909
772	3892
773	3972
774	4040
775	3997
776	3950
777	3932
778	3903
779	3724
780	3782
781	3772
782	3907
783	3836
784	3944
785	3871
786	3906
787	3803
788	3898
789	3763
790	3779
791	3742
792	3857
793	3706
794	3683
795	3714
796	3804
797	3727
798	3721
799	3623
800	3724
801	3715
802	3728
803	3806
804	3654
805	3628
806	3669
807	3658
808	3567
809	3543
810	3572
811	3717
812	3669
813	3764
814	3741
815	3541
816	3586
817	3651
818	3577
819	3634
820	3592
821	3532
822	3523
823	3549
824	3629
825	3432
826	3582
827	3490
828	3407
829	3487
830	3382
831	3489
832	3464
833	3432
834	3543
835	3404
836	3346
837	3520
838	3464
839	3446
840	3481
841	3479
842	3529
843	3467
844	3448
845	3425
846	3280
847	3330
848	3324
849	3417
850	3299
851	3455
852	3283
853	3322
854	3297
855	3304
856	3398
857	3351
858	3195
859	3435
860	3305
861	3390
862	3386
863	3335
864	3263
865	3297
866	3366
867	3261
868	3249
869	3229
870	3214
871	3323
872	3216
873	3344
874	3309
875	3189
876	3183
877	3163
878	3270
879	3184
880	3173
881	3193
882	3157
883	3175
884	3104
885	3211
886	3246
887	3212
888	3191
889	3188
890	3142
891	3107
892	3085
893	3196
894	3202
895	3113
896	2989
897	3056
898	3099
899	3071
900	3107
901	2990
902	3046
903	3088
904	3044
905	3113
906	2929
907	3073
908	3030
909	3050
910	3010
911	3068
912	3053
913	2994
914	2969
915	2967
916	3073
917	2973
918	3044
919	3104
920	2876
921	2967
922	2860
923	2778
924	2840
925	2879
926	2958
927	2884
928	2897
929	2839
930	2826
931	2792
932	2851
933	2789
934	2784
935	2864
936	2704
937	2861
938	2867
939	2776
940	2804
941	2894
942	2835
943	2880
944	2813
945	2861
946	2827
947	2821
948	2705
949	2735
950	2677
951	2729
952	2834
953	2720
954	2699
955	2772
956	2791
957	2660
958	2635
959	2698
960	2653
961	2684
962	2611
963	2742
964	2692
965	2581
966	2596
967	2668
968	2552
969	2638
970	2551
971	2544
972	2549
973	2553
974	2623
975	2514
976	2558
977	2522
978	2593
979	2510
980	2447
981	2535
982	2522
983	2490
984	2555
985	2567
986	2400
987	2380
988	2400
989	2394
990	2479
991	2473
992	2417
993	2515
994	2518
995	2461
996	2454
997	2451
998	2472
999	2334
1000	10812044