1	2774814852
2	192655089
3	45211784
4	23233294
5	19699540
6	20715928
7	23487190
8	27371168
9	31797197
10	36669299
11	41397942
12	46133973
13	50818513
14	54991873
15	58450701
16	61499413
17	64035272
18	66020125
19	67456398
20	68529129
21	69227397
22	69515693
23	69416196
24	69143103
25	68636974
26	67885490
27	66755093
28	65545143
29	64498336
30	63370083
31	61761417
32	60031657
33	58165831
34	56163107
35	54131362
36	51800376
37	49292023
38	46685828
39	44002061
40	41349389
41	38586760
42	35799969
43	33035587
44	30359129
45	27551923
46	24874539
47	22314365
48	19873790
49	17594633
50	15532660
51	13560028
52	11773014
53	10156605
54	8707411
55	7445906
56	6328884
57	5380222
58	4567949
59	3870983
60	3278779
61	2785965
62	2376478
63	2024191
64	1749483
65	1530684
66	1344518
67	1196645
68	1083396
69	989794
70	916721
71	853118
72	803851
73	760067
74	725477
75	696631
76	673921
77	652758
78	637165
79	615191
80	599700
81	578092
82	560442
83	545032
84	533046
85	516494
86	499535
87	484967
88	471661
89	457118
90	442375
91	426688
92	412871
93	399716
94	385294
95	370129
96	359571
97	350711
98	337977
99	327569
100	318520
101	309003
102	300587
103	292704
104	285755
105	280092
106	270948
107	264096
108	260751
109	253664
110	248074
111	242045
112	236499
113	235267
114	229636
115	224976
116	221745
117	217106
118	212459
119	208809
120	204550
121	200176
122	195481
123	191556
124	190020
125	184848
126	181010
127	178654
128	175350
129	171205
130	167839
131	166769
132	163142
133	159525
134	156010
135	153492
136	153007
137	151544
138	149474
139	147365
140	144932
141	142881
142	140576
143	138145
144	135120
145	134092
146	130599
147	129337
148	126998
149	124092
150	122961
151	119176
152	116913
153	115324
154	113861
155	112025
156	111645
157	110444
158	108668
159	106447
160	105917
161	104662
162	102957
163	100613
164	99512
165	98676
166	96211
167	93951
168	93306
169	91869
170	89022
171	87716
172	87866
173	86601
174	84690
175	83917
176	83616
177	82656
178	81558
179	79454
180	77648
181	78139
182	75956
183	75973
184	74268
185	73316
186	71336
187	70858
188	70463
189	68616
190	67925
191	67182
192	66773
193	65189
194	65686
195	64540
196	63977
197	63687
198	62462
199	62723
200	61333
201	60751
202	59991
203	59108
204	57456
205	57380
206	56741
207	56255
208	54903
209	54876
210	55447
211	54949
212	53887
213	53403
214	52725
215	52062
216	52673
217	51841
218	50719
219	50662
220	50010
221	49387
222	49069
223	48408
224	47759
225	47539
226	47274
227	46545
228	46774
229	45112
230	45433
231	45419
232	44486
233	43544
234	43660
235	42879
236	43170
237	43010
238	42386
239	42099
240	41773
241	40318
242	40386
243	40228
244	39861
245	39311
246	39243
247	38722
248	38639
249	38684
250	37698
251	37644
252	37177
253	36863
254	36584
255	36636
256	36614
257	36061
258	35263
259	35853
260	34751
261	34463
262	35001
263	34317
264	33808
265	33763
266	33499
267	33407
268	32448
269	33048
270	32812
271	32068
272	31859
273	31392
274	31305
275	31273
276	31182
277	30701
278	30104
279	29873
280	29916
281	29392
282	29616
283	29989
284	29458
285	28991
286	28793
287	28717
288	28531
289	28569
290	28149
291	27164
292	27065
293	27023
294	26869
295	26763
296	27264
297	26161
298	26073
299	26177
300	25763
301	26222
302	25850
303	25471
304	24955
305	24938
306	25043
307	24566
308	24802
309	24394
310	24051
311	23866
312	24064
313	23916
314	23644
315	23326
316	23376
317	22877
318	23026
319	22548
320	22471
321	22217
322	22568
323	22582
324	22302
325	21945
326	21645
327	21346
328	21458
329	21658
330	21466
331	21331
332	20797
333	20844
334	20787
335	21107
336	20428
337	20348
338	20270
339	19966
340	19980
341	19702
342	19645
343	19735
344	19372
345	20110
346	19361
347	19468
348	19286
349	19120
350	19025
351	18810
352	18903
353	18779
354	18870
355	18419
356	18526
357	18759
358	18105
359	18562
360	18076
361	18003
362	17708
363	17616
364	17945
365	17447
366	17357
367	17320
368	17170
369	16890
370	16955
371	16875
372	16692
373	16828
374	16698
375	16329
376	16200
377	16346
378	16065
379	16130
380	15906
381	15619
382	15676
383	15732
384	15854
385	15473
386	15651
387	15259
388	15546
389	15263
390	15203
391	15191
392	15178
393	15119
394	15286
395	15045
396	14735
397	14530
398	14596
399	14542
400	14443
401	14242
402	14304
403	14247
404	13845
405	13861
406	14135
407	14366
408	14281
409	14344
410	14265
411	14196
412	13693
413	13603
414	13485
415	13287
416	13506
417	13568
418	13450
419	13568
420	13292
421	13026
422	12984
423	12813
424	12877
425	12966
426	12673
427	12719
428	12809
429	12841
430	12409
431	12346
432	12477
433	12529
434	12378
435	12441
436	12091
437	12379
438	12443
439	12094
440	12005
441	12112
442	12038
443	12117
444	12126
445	11978
446	11691
447	11662
448	11426
449	11493
450	11702
451	11604
452	11466
453	11503
454	11568
455	11180
456	11213
457	11343
458	11357
459	11103
460	10902
461	10857
462	11117
463	10951
464	11089
465	10808
466	10938
467	10758
468	10858
469	10836
470	10638
471	10858
472	10444
473	10435
474	10609
475	10649
476	10235
477	10577
478	10222
479	10143
480	10199
481	10262
482	10011
483	10072
484	10002
485	10069
486	10113
487	10042
488	10246
489	9837
490	9782
491	10162
492	9984
493	9901
494	9796
495	10054
496	9983
497	9725
498	9622
499	9546
500	9448
501	9750
502	9341
503	9681
504	9768
505	9421
506	9433
507	9312
508	9367
509	9021
510	9195
511	9077
512	8934
513	8951
514	9037
515	9043
516	8746
517	8678
518	8654
519	8815
520	8876
521	8877
522	8900
523	8641
524	8765
525	8959
526	8574
527	8460
528	8595
529	8388
530	8467
531	8509
532	8494
533	8494
534	8492
535	8398
536	8374
537	8312
538	8237
539	8405
540	8082
541	8342
542	8170
543	8013
544	7878
545	8079
546	7900
547	7891
548	7810
549	7880
550	7750
551	7741
552	7767
553	7899
554	7781
555	7765
556	7668
557	7628
558	7685
559	7720
560	7546
561	7559
562	7671
563	7495
564	7528
565	7373
566	7420
567	7506
568	7255
569	7098
570	7135
571	7252
572	7293
573	7279
574	7326
575	7419
576	7221
577	7113
578	6960
579	7154
580	7028
581	6926
582	7007
583	6887
584	6992
585	6725
586	6886
587	6816
588	6880
589	6862
590	7017
591	6872
592	6861
593	6874
594	6777
595	6892
596	6854
597	6721
598	6816
599	6638
600	6689
601	6550
602	6648
603	6424
604	6423
605	6574
606	6495
607	6381
608	6442
609	6348
610	6287
611	6280
612	6528
613	6381
614	6338
615	6323
616	6424
617	6281
618	6151
619	6184
620	6163
621	6166
622	6093
623	6103
624	6012
625	5885
626	6233
627	6276
628	6166
629	5978
630	6038
631	6008
632	5898
633	5781
634	5716
635	5814
636	5809
637	5892
638	5953
639	5781
640	5817
641	5799
642	5867
643	5813
644	5691
645	5795
646	5784
647	5849
648	5749
649	5788
650	5688
651	5568
652	5413
653	5597
654	5686
655	5511
656	5499
657	5653
658	5501
659	5605
660	5560
661	5576
662	5665
663	5544
664	5427
665	5353
666	5637
667	5515
668	5454
669	5612
670	5383
671	5402
672	5395
673	5356
674	5205
675	5386
676	5289
677	5212
678	5205
679	5083
680	5092
681	5202
682	5081
683	5233
684	5147
685	4986
686	5183
687	5204
688	5068
689	5090
690	5013
691	5011
692	4929
693	4903
694	4796
695	4838
696	4999
697	4914
698	4976
699	4919
700	4787
701	4949
702	4970
703	4927
704	4945
705	4949
706	4945
707	4642
708	4730
709	4829
710	4963
711	4928
712	4759
713	4664
714	4685
715	4619
716	4925
717	4895
718	4710
719	4769
720	4688
721	4703
722	4624
723	4847
724	4597
725	4701
726	4639
727	4439
728	4497
729	4644
730	4700
731	4690
732	4508
733	4459
734	4561
735	4611
736	4504
737	4418
738	4499
739	4417
740	4604
741	4772
742	4541
743	4587
744	4489
745	4409
746	4280
747	4338
748	4387
749	4404
750	4494
751	4339
752	4369
753	4341
754	4464
755	4436
756	4395
757	4345
758	4294
759	4342
760	4341
761	4400
762	4434
763	4338
764	4387
765	4210
766	4329
767	4251
768	4221
769	4194
770	4155
771	4035
772	4186
773	4189
774	4204
775	4173
776	4095
777	4044
778	4125
779	4080
780	4134
781	4075
782	3990
783	3913
784	3889
785	3988
786	4020
787	3938
788	3947
789	3974
790	3936
791	3968
792	4031
793	3945
794	3924
795	4043
796	3915
797	3953
798	3929
799	3854
800	3768
801	3796
802	3995
803	3908
804	3822
805	3970
806	3880
807	3808
808	3941
809	3737
810	3716
811	3785
812	3792
813	3697
814	3811
815	3674
816	3681
817	3888
818	3768
819	3733
820	3576
821	3642
822	3672
823	3650
824	3673
825	3853
826	3737
827	3625
828	3623
829	3695
830	3607
831	3604
832	3599
833	3508
834	3494
835	3662
836	3533
837	3621
838	3638
839	3522
840	3507
841	3538
842	3558
843	3490
844	3570
845	3471
846	3716
847	3542
848	3455
849	3496
850	3513
851	3418
852	3530
853	3507
854	3526
855	3553
856	3396
857	3526
858	3370
859	3494
860	3516
861	3480
862	3545
863	3344
864	3308
865	3334
866	3238
867	3350
868	3396
869	3511
870	3390
871	3382
872	3261
873	3368
874	3301
875	3277
876	3281
877	3360
878	3313
879	3352
880	3326
881	3285
882	3117
883	3134
884	3240
885	3229
886	3194
887	3272
888	3231
889	3244
890	3115
891	3242
892	3311
893	3158
894	3279
895	3172
896	3228
897	3242
898	3236
899	3192
900	3274
901	3129
902	3073
903	3142
904	3159
905	3198
906	3022
907	3169
908	3107
909	3167
910	3268
911	3149
912	3102
913	3098
914	3075
915	3123
916	3129
917	3118
918	3056
919	3147
920	3007
921	3091
922	2959
923	2924
924	2899
925	2989
926	3017
927	3030
928	3042
929	3012
930	2884
931	2921
932	2874
933	2956
934	2957
935	2945
936	2940
937	2908
938	2810
939	2883
940	2949
941	2913
942	2893
943	2903
944	2850
945	2815
946	2743
947	2813
948	2861
949	2713
950	2841
951	2903
952	2715
953	2785
954	2964
955	2902
956	2813
957	2869
958	2843
959	2778
960	2907
961	2891
962	2839
963	2911
964	2824
965	2819
966	2744
967	2755
968	2657
969	2727
970	2637
971	2680
972	2684
973	2778
974	2758
975	2704
976	2686
977	2702
978	2701
979	2675
980	2770
981	2726
982	2683
983	2735
984	2658
985	2640
986	2640
987	2674
988	2583
989	2648
990	2686
991	2554
992	2486
993	2579
994	2601
995	2471
996	2485
997	2577
998	2589
999	2549
1000	11960007