1	553639294
2	57742739
3	17085709
4	7402434
5	3930222
6	2372957
7	1584584
8	1141701
9	878484
10	735232
11	644276
12	599477
13	569456
14	567892
15	588954
16	629116
17	673062
18	731332
19	800250
20	882917
21	978844
22	1104597
23	1206386
24	1321352
25	1448744
26	1597313
27	1758263
28	1941010
29	2112796
30	2308041
31	2499737
32	2720618
33	2958945
34	3230160
35	3479450
36	3735737
37	4012516
38	4310781
39	4591709
40	4905721
41	5214642
42	5499061
43	5713661
44	5902906
45	6054596
46	6166404
47	6210691
48	6237529
49	6217747
50	6126497
51	5990539
52	5779335
53	5579249
54	5287240
55	4973136
56	4627467
57	4283198
58	3945619
59	3599095
60	3252015
61	2953863
62	2660936
63	2422855
64	2193327
65	2002538
66	1862225
67	1738843
68	1653435
69	1600347
70	1568043
71	1565023
72	1567927
73	1602045
74	1643806
75	1684784
76	1735498
77	1794573
78	1857878
79	1926370
80	1998013
81	2079635
82	2148717
83	2245405
84	2320672
85	2404134
86	2471424
87	2547409
88	2633046
89	2695238
90	2770626
91	2827176
92	2882897
93	2919510
94	2962654
95	2996021
96	3027897
97	3048037
98	3058213
99	3051510
100	3045294
101	3009706
102	2976421
103	2922282
104	2837314
105	2761221
106	2660818
107	2559893
108	2453492
109	2343274
110	2229035
111	2111921
112	1987381
113	1858239
114	1747631
115	1618673
116	1491821
117	1374605
118	1260907
119	1142438
120	1054129
121	956998
122	878617
123	794587
124	721933
125	652088
126	589004
127	540812
128	493607
129	449609
130	412519
131	377551
132	348295
133	327371
134	306745
135	295104
136	283595
137	272880
138	268649
139	262416
140	258976
141	259125
142	252547
143	251904
144	252279
145	250805
146	248853
147	246390
148	245340
149	240630
150	239118
151	236533
152	232852
153	233911
154	227925
155	221872
156	222319
157	216495
158	214240
159	211151
160	206255
161	201389
162	199983
163	194379
164	190668
165	184333
166	181736
167	177519
168	175125
169	171245
170	168069
171	164133
172	159076
173	153883
174	154067
175	150135
176	146712
177	141421
178	137637
179	136476
180	133279
181	130369
182	128045
183	127766
184	125027
185	124504
186	123652
187	124406
188	124286
189	123297
190	122639
191	120570
192	119216
193	119548
194	119081
195	117562
196	117063
197	118021
198	116138
199	116144
200	116230
201	115651
202	114929
203	114991
204	111941
205	111180
206	109923
207	109448
208	107921
209	107749
210	105818
211	104857
212	102992
213	99520
214	97481
215	96213
216	95357
217	94639
218	94413
219	92669
220	91330
221	89138
222	86684
223	85562
224	85187
225	82739
226	81407
227	79408
228	78365
229	76709
230	74938
231	73927
232	72416
233	70951
234	69830
235	69836
236	68025
237	67413
238	66320
239	65604
240	65136
241	64393
242	63608
243	63176
244	62060
245	62237
246	62592
247	61720
248	61484
249	61557
250	61313
251	60795
252	61800
253	60598
254	59302
255	57332
256	57390
257	56643
258	56315
259	56533
260	55415
261	55072
262	54540
263	54446
264	53171
265	52640
266	53049
267	51999
268	52007
269	51189
270	50822
271	49803
272	48729
273	47124
274	47801
275	47496
276	46205
277	45760
278	45119
279	44585
280	44622
281	44365
282	44287
283	43470
284	43005
285	42949
286	43079
287	42245
288	41281
289	40922
290	40592
291	40087
292	39967
293	39784
294	39191
295	39168
296	39149
297	38571
298	38683
299	38580
300	38650
301	39017
302	38511
303	38339
304	38305
305	37311
306	37097
307	36550
308	36516
309	35159
310	35542
311	35153
312	34420
313	34003
314	34168
315	34359
316	33573
317	33153
318	33748
319	33616
320	33429
321	33272
322	32636
323	33363
324	33061
325	32267
326	32443
327	31581
328	31624
329	31151
330	30613
331	29748
332	29899
333	29528
334	29365
335	29436
336	29560
337	29465
338	28676
339	28492
340	28667
341	27913
342	28019
343	27820
344	27494
345	27428
346	27190
347	27187
348	26481
349	26761
350	26895
351	26201
352	26247
353	26042
354	26076
355	25797
356	24965
357	25852
358	25443
359	24772
360	24525
361	24370
362	23851
363	24021
364	23568
365	24081
366	23153
367	23127
368	22849
369	22677
370	22940
371	22462
372	22707
373	22331
374	22340
375	22795
376	22701
377	22441
378	22094
379	22242
380	22544
381	22218
382	22186
383	21962
384	21440
385	21104
386	20717
387	21008
388	20622
389	20537
390	20223
391	19864
392	19755
393	19181
394	19375
395	19147
396	19000
397	19420
398	18988
399	19647
400	19419
401	19318
402	18702
403	18542
404	18445
405	18403
406	18620
407	18251
408	17889
409	18061
410	17877
411	17628
412	17577
413	17519
414	17569
415	17368
416	17565
417	17453
418	17550
419	17256
420	16994
421	16510
422	16472
423	16605
424	16660
425	16526
426	16276
427	16689
428	16447
429	16448
430	16496
431	16353
432	15892
433	16157
434	16084
435	16055
436	15818
437	15989
438	15514
439	15766
440	15612
441	15398
442	15400
443	15218
444	15766
445	15383
446	15476
447	15561
448	15350
449	14954
450	14909
451	14780
452	15261
453	14327
454	14095
455	14137
456	14378
457	14385
458	14002
459	14036
460	13830
461	13466
462	13310
463	13591
464	13113
465	13260
466	13316
467	13757
468	13477
469	13424
470	13462
471	13583
472	12972
473	13012
474	12836
475	12729
476	13053
477	12938
478	12695
479	12586
480	13079
481	13109
482	13036
483	12571
484	12645
485	12883
486	12306
487	12342
488	12370
489	12214
490	12106
491	12022
492	12110
493	12446
494	11893
495	11864
496	11212
497	11774
498	11700
499	11996
500	11943
501	11914
502	11320
503	11692
504	11419
505	11655
506	11316
507	11438
508	11650
509	11703
510	11077
511	11452
512	11325
513	11753
514	11379
515	11195
516	10883
517	10999
518	10909
519	10787
520	10642
521	10745
522	10744
523	10573
524	10532
525	10307
526	9972
527	10207
528	10385
529	10221
530	10271
531	10155
532	10406
533	10383
534	10258
535	10173
536	9991
537	10017
538	9908
539	10339
540	9897
541	10077
542	9813
543	9801
544	9817
545	9954
546	9702
547	9589
548	9469
549	9147
550	9525
551	9477
552	9412
553	9131
554	9301
555	9111
556	9073
557	8913
558	9124
559	9440
560	9173
561	8974
562	8770
563	8951
564	8878
565	9086
566	9111
567	9072
568	8855
569	8964
570	8835
571	9022
572	9227
573	8996
574	9023
575	9234
576	8684
577	8726
578	8543
579	8749
580	8618
581	8831
582	8979
583	8580
584	8546
585	8827
586	8595
587	8553
588	8446
589	8709
590	8038
591	8174
592	8167
593	8139
594	8134
595	8111
596	8039
597	8131
598	8199
599	8197
600	7784
601	7703
602	8080
603	7608
604	7678
605	7626
606	7590
607	7734
608	7371
609	7345
610	7587
611	7204
612	7277
613	7277
614	7333
615	7494
616	7670
617	7325
618	7555
619	7374
620	7290
621	7273
622	7097
623	6913
624	6796
625	6813
626	7010
627	6780
628	6700
629	6794
630	6860
631	6919
632	6875
633	6998
634	6894
635	6850
636	6888
637	6871
638	6942
639	6769
640	6797
641	6756
642	6682
643	6658
644	6713
645	6683
646	6534
647	6626
648	6500
649	6368
650	6678
651	6417
652	6123
653	6266
654	6326
655	6381
656	6528
657	6472
658	6428
659	6173
660	6326
661	6106
662	6070
663	6117
664	6121
665	6276
666	6269
667	6225
668	6065
669	6236
670	6205
671	6240
672	6042
673	6115
674	6093
675	5860
676	5706
677	5789
678	5649
679	5729
680	5485
681	5627
682	5817
683	5757
684	5891
685	5705
686	5631
687	5510
688	5534
689	5468
690	5612
691	5641
692	5636
693	5513
694	5567
695	5658
696	5520
697	5689
698	5497
699	5202
700	5355
701	5415
702	5458
703	5499
704	5431
705	5339
706	5290
707	5041
708	5229
709	5173
710	5288
711	5303
712	5183
713	5007
714	5181
715	5035
716	5002
717	5023
718	5174
719	5253
720	5152
721	4975
722	5116
723	5060
724	4966
725	4990
726	4892
727	4917
728	4935
729	5040
730	4994
731	4768
732	4903
733	4869
734	4957
735	4814
736	4765
737	4702
738	4712
739	4640
740	4586
741	4547
742	4646
743	4662
744	4634
745	4515
746	4582
747	4397
748	4616
749	4510
750	4616
751	4743
752	4561
753	4557
754	4602
755	4680
756	4689
757	4624
758	4497
759	4689
760	4646
761	4632
762	4634
763	4676
764	4618
765	4522
766	4582
767	4489
768	4588
769	4452
770	4468
771	4682
772	4474
773	4628
774	4576
775	4553
776	4337
777	4386
778	4155
779	4371
780	4303
781	4260
782	4391
783	4402
784	4274
785	3999
786	4170
787	4066
788	4151
789	4088
790	4062
791	4098
792	4169
793	4098
794	4220
795	4200
796	4032
797	4017
798	4057
799	4255
800	3962
801	3921
802	3971
803	3860
804	3975
805	3912
806	4125
807	4001
808	4017
809	3978
810	3779
811	3887
812	4039
813	4041
814	3955
815	4156
816	3927
817	3983
818	4168
819	3922
820	3910
821	3821
822	3820
823	3792
824	3588
825	3746
826	3562
827	3511
828	3646
829	3722
830	3756
831	3747
832	3779
833	3748
834	3685
835	3678
836	3680
837	3460
838	3480
839	3560
840	3426
841	3576
842	3601
843	3511
844	3525
845	3569
846	3577
847	3636
848	3589
849	3617
850	3465
851	3399
852	3458
853	3434
854	3515
855	3423
856	3490
857	3524
858	3629
859	3499
860	3486
861	3479
862	3488
863	3592
864	3476
865	3237
866	3375
867	3507
868	3495
869	3515
870	3471
871	3424
872	3529
873	3467
874	3389
875	3234
876	3344
877	3436
878	3447
879	3347
880	3529
881	3335
882	3314
883	3290
884	3398
885	3330
886	3170
887	3188
888	3222
889	3259
890	3174
891	3127
892	3170
893	3178
894	3131
895	2998
896	3206
897	3103
898	3170
899	3057
900	3378
901	3190
902	3126
903	3037
904	3013
905	3113
906	3014
907	3093
908	3063
909	3048
910	3070
911	2996
912	2998
913	3027
914	2982
915	3050
916	3045
917	3048
918	3130
919	3038
920	2937
921	2989
922	3261
923	3016
924	3090
925	3025
926	2969
927	2885
928	2948
929	2939
930	3064
931	3071
932	2910
933	2815
934	2741
935	2945
936	2950
937	2941
938	3009
939	2774
940	2775
941	2749
942	2888
943	2881
944	2709
945	2827
946	2816
947	2884
948	2884
949	2821
950	2828
951	2812
952	2787
953	2894
954	2752
955	2802
956	2813
957	2772
958	2629
959	2741
960	2749
961	2699
962	2738
963	2599
964	2472
965	2546
966	2594
967	2483
968	2532
969	2603
970	2555
971	2522
972	2547
973	2580
974	2543
975	2734
976	2725
977	2783
978	2654
979	2652
980	2659
981	2697
982	2591
983	2508
984	2543
985	2482
986	2529
987	2746
988	2689
989	2513
990	2566
991	2539
992	2535
993	2449
994	2637
995	2514
996	2529
997	2500
998	2415
999	2422
1000	8574618