1	4573604428
2	426487699
3	142089175
4	74533054
5	43151359
6	35778152
7	32291147
8	32585270
9	33380311
10	34702263
11	35976003
12	37134472
13	38051044
14	38783036
15	39235212
16	39459372
17	39430567
18	39194097
19	38826430
20	38210296
21	37465333
22	36590518
23	35620418
24	34499648
25	33347588
26	32136013
27	30841360
28	29529047
29	28200467
30	26853698
31	25534701
32	24215996
33	22939086
34	21650619
35	20441079
36	19248674
37	18085713
38	17009761
39	15916365
40	14921406
41	13948748
42	13031060
43	12169393
44	11333271
45	10576271
46	9825699
47	9133255
48	8494750
49	7886205
50	7317945
51	6799482
52	6313245
53	5845480
54	5422019
55	5016883
56	4648440
57	4306842
58	3988474
59	3684033
60	3424479
61	3168599
62	2935799
63	2720732
64	2521896
65	2335682
66	2164855
67	2009832
68	1861263
69	1733586
70	1608464
71	1496899
72	1390542
73	1298071
74	1204414
75	1126584
76	1052477
77	983956
78	918170
79	861447
80	804845
81	756341
82	707442
83	665323
84	624413
85	588971
86	556573
87	525892
88	496900
89	469443
90	444418
91	420595
92	396186
93	376759
94	358798
95	340749
96	324381
97	308684
98	295943
99	283953
100	270348
101	258351
102	248986
103	237902
104	227210
105	218452
106	209270
107	200725
108	193238
109	187030
110	180869
111	173045
112	167120
113	161347
114	156055
115	149710
116	145671
117	140036
118	136337
119	132345
120	127890
121	123894
122	120264
123	116913
124	113545
125	109993
126	106575
127	103782
128	100467
129	98139
130	95338
131	92709
132	90821
133	88083
134	85847
135	83722
136	81513
137	79666
138	78080
139	75945
140	74787
141	73118
142	70978
143	69411
144	67644
145	65917
146	64833
147	62999
148	61961
149	60664
150	59123
151	58376
152	57572
153	56323
154	54925
155	53904
156	53323
157	51843
158	51179
159	50374
160	49255
161	48679
162	48089
163	47179
164	46238
165	45369
166	45112
167	44102
168	43670
169	42971
170	42312
171	41611
172	41120
173	40595
174	39953
175	39814
176	39321
177	38881
178	37879
179	37262
180	37369
181	36698
182	36035
183	36032
184	35230
185	35074
186	34736
187	34261
188	33621
189	33236
190	32668
191	32220
192	31708
193	31401
194	31270
195	30726
196	30691
197	30626
198	29953
199	29576
200	29436
201	29199
202	28557
203	28156
204	27947
205	27908
206	27761
207	26997
208	26882
209	26458
210	26031
211	26087
212	25688
213	25542
214	25303
215	25082
216	24415
217	24063
218	24025
219	23591
220	23708
221	23571
222	23391
223	23268
224	22905
225	22989
226	22507
227	22345
228	21925
229	21892
230	21983
231	21726
232	21409
233	21354
234	21253
235	20996
236	20694
237	20134
238	20069
239	20159
240	20025
241	19842
242	19542
243	19462
244	19216
245	19252
246	19263
247	18899
248	18906
249	18642
250	18279
251	18180
252	18026
253	17686
254	17594
255	17420
256	17395
257	17140
258	16872
259	16899
260	17086
261	16466
262	16392
263	16331
264	16529
265	16186
266	16070
267	15883
268	15915
269	15703
270	15614
271	15450
272	15500
273	15037
274	14925
275	15071
276	14795
277	14577
278	14466
279	14416
280	14554
281	14405
282	14157
283	14115
284	14106
285	13870
286	13792
287	13582
288	13476
289	13277
290	13465
291	13304
292	13229
293	13163
294	12966
295	12748
296	12878
297	12608
298	12781
299	12874
300	12785
301	12624
302	12339
303	12326
304	12156
305	12142
306	12069
307	11865
308	11699
309	11821
310	11581
311	11334
312	11576
313	11213
314	11217
315	11314
316	11151
317	11032
318	10962
319	10846
320	11003
321	10853
322	10781
323	10731
324	10601
325	10737
326	10587
327	10404
328	10423
329	10420
330	10270
331	10317
332	10145
333	10072
334	10047
335	9942
336	10051
337	9878
338	9836
339	9791
340	9754
341	9653
342	9571
343	9481
344	9552
345	9528
346	9403
347	9346
348	9400
349	9396
350	9122
351	9039
352	9110
353	9058
354	8943
355	8895
356	9060
357	8777
358	8968
359	8753
360	8708
361	8661
362	8626
363	8691
364	8617
365	8643
366	8421
367	8402
368	8484
369	8457
370	8211
371	8338
372	8090
373	7969
374	8087
375	7987
376	7985
377	7930
378	7895
379	7819
380	7587
381	7809
382	7635
383	7487
384	7512
385	7548
386	7571
387	7313
388	7506
389	7591
390	7366
391	7433
392	7361
393	7349
394	7257
395	7089
396	7268
397	7310
398	7103
399	7095
400	6994
401	6970
402	6969
403	6941
404	6910
405	6784
406	6813
407	6742
408	6764
409	6846
410	6783
411	6588
412	6665
413	6732
414	6488
415	6582
416	6552
417	6500
418	6473
419	6602
420	6308
421	6350
422	6235
423	6238
424	6223
425	6217
426	6204
427	6148
428	6185
429	6115
430	6208
431	6136
432	6140
433	6158
434	5962
435	6072
436	5960
437	5858
438	5992
439	5944
440	5841
441	5853
442	5913
443	5676
444	5750
445	5668
446	5748
447	5653
448	5562
449	5656
450	5609
451	5544
452	5513
453	5419
454	5561
455	5422
456	5401
457	5495
458	5441
459	5507
460	5332
461	5412
462	5327
463	5339
464	5337
465	5324
466	5301
467	5241
468	5239
469	5031
470	5178
471	5230
472	5169
473	5116
474	5041
475	4884
476	5071
477	4900
478	5019
479	5085
480	4982
481	5024
482	4885
483	5015
484	4985
485	4706
486	4951
487	4904
488	4839
489	4773
490	4776
491	4751
492	4701
493	4806
494	4686
495	4643
496	4605
497	4653
498	4671
499	4561
500	4616
501	4520
502	4561
503	4503
504	4574
505	4556
506	4414
507	4456
508	4367
509	4311
510	4505
511	4485
512	4355
513	4455
514	4307
515	4435
516	4414
517	4278
518	4381
519	4245
520	4255
521	4206
522	4253
523	4323
524	4162
525	4191
526	4018
527	4218
528	4180
529	4145
530	4107
531	4086
532	4196
533	4134
534	4131
535	4032
536	4062
537	3943
538	4006
539	4031
540	3940
541	3778
542	3919
543	3863
544	3932
545	3910
546	3898
547	3889
548	3830
549	3768
550	3726
551	3742
552	3761
553	3997
554	3782
555	3769
556	3756
557	3815
558	3790
559	3704
560	3702
561	3722
562	3710
563	3589
564	3673
565	3615
566	3641
567	3538
568	3600
569	3613
570	3525
571	3496
572	3603
573	3517
574	3354
575	3467
576	3522
577	3585
578	3416
579	3516
580	3419
581	3410
582	3314
583	3372
584	3397
585	3477
586	3370
587	3377
588	3269
589	3397
590	3329
591	3259
592	3386
593	3260
594	3284
595	3281
596	3241
597	3216
598	3392
599	3254
600	3287
601	3274
602	3159
603	3284
604	3208
605	3108
606	3154
607	3180
608	3171
609	3135
610	3198
611	3126
612	3129
613	3140
614	3054
615	3036
616	3062
617	3091
618	3092
619	3127
620	2984
621	3036
622	3000
623	3011
624	3026
625	3041
626	3069
627	2956
628	2935
629	2952
630	2925
631	2868
632	2888
633	2960
634	2956
635	2850
636	2895
637	2853
638	2807
639	2987
640	2890
641	2824
642	2789
643	2732
644	2856
645	2819
646	2738
647	2820
648	2716
649	2778
650	2725
651	2626
652	2772
653	2646
654	2700
655	2799
656	2646
657	2567
658	2704
659	2681
660	2680
661	2668
662	2605
663	2650
664	2539
665	2696
666	2558
667	2662
668	2539
669	2555
670	2569
671	2551
672	2618
673	2651
674	2616
675	2599
676	2494
677	2655
678	2587
679	2506
680	2574
681	2531
682	2538
683	2525
684	2498
685	2449
686	2492
687	2469
688	2507
689	2485
690	2465
691	2442
692	2428
693	2496
694	2466
695	2357
696	2356
697	2393
698	2576
699	2433
700	2433
701	2453
702	2378
703	2302
704	2448
705	2403
706	2314
707	2264
708	2351
709	2344
710	2376
711	2368
712	2345
713	2417
714	2324
715	2311
716	2215
717	2331
718	2291
719	2264
720	2297
721	2226
722	2255
723	2208
724	2306
725	2218
726	2236
727	2314
728	2192
729	2260
730	2240
731	2272
732	2179
733	2217
734	2228
735	2155
736	2163
737	2132
738	2177
739	2152
740	2142
741	2189
742	2170
743	2172
744	2180
745	2121
746	2071
747	2125
748	2078
749	2086
750	2103
751	2101
752	2147
753	2096
754	2082
755	2049
756	2085
757	2083
758	1993
759	2000
760	2000
761	2034
762	2069
763	1986
764	1999
765	1883
766	1988
767	1967
768	1915
769	1956
770	1925
771	1970
772	1998
773	2075
774	1925
775	1982
776	1920
777	1889
778	1947
779	1987
780	1928
781	1912
782	1920
783	1885
784	1859
785	1931
786	1907
787	1976
788	1786
789	1877
790	1872
791	1797
792	1891
793	1905
794	1923
795	1838
796	1932
797	1828
798	1854
799	1819
800	1789
801	1813
802	1851
803	1842
804	1775
805	1843
806	1798
807	1805
808	1843
809	1736
810	1840
811	1785
812	1762
813	1782
814	1709
815	1801
816	1750
817	1761
818	1744
819	1807
820	1864
821	1790
822	1838
823	1786
824	1805
825	1767
826	1772
827	1783
828	1809
829	1687
830	1772
831	1673
832	1697
833	1722
834	1644
835	1756
836	1718
837	1679
838	1706
839	1598
840	1648
841	1619
842	1635
843	1639
844	1625
845	1659
846	1667
847	1730
848	1649
849	1696
850	1635
851	1676
852	1591
853	1630
854	1579
855	1593
856	1554
857	1615
858	1661
859	1678
860	1612
861	1571
862	1617
863	1621
864	1623
865	1626
866	1591
867	1531
868	1582
869	1499
870	1541
871	1560
872	1538
873	1511
874	1576
875	1522
876	1561
877	1504
878	1460
879	1524
880	1508
881	1493
882	1502
883	1517
884	1425
885	1529
886	1467
887	1494
888	1475
889	1419
890	1463
891	1518
892	1462
893	1426
894	1433
895	1482
896	1469
897	1463
898	1454
899	1424
900	1371
901	1392
902	1502
903	1415
904	1434
905	1437
906	1473
907	1441
908	1426
909	1461
910	1499
911	1446
912	1477
913	1375
914	1417
915	1476
916	1379
917	1470
918	1404
919	1335
920	1364
921	1406
922	1478
923	1438
924	1378
925	1413
926	1360
927	1427
928	1413
929	1404
930	1347
931	1422
932	1429
933	1335
934	1378
935	1334
936	1393
937	1466
938	1333
939	1347
940	1369
941	1372
942	1320
943	1398
944	1292
945	1384
946	1287
947	1293
948	1325
949	1342
950	1310
951	1379
952	1332
953	1335
954	1291
955	1291
956	1306
957	1271
958	1218
959	1294
960	1313
961	1281
962	1272
963	1334
964	1260
965	1357
966	1292
967	1227
968	1181
969	1302
970	1271
971	1289
972	1301
973	1223
974	1208
975	1198
976	1256
977	1232
978	1236
979	1218
980	1187
981	1223
982	1201
983	1279
984	1167
985	1133
986	1145
987	1175
988	1226
989	1249
990	1173
991	1192
992	1173
993	1214
994	1176
995	1169
996	1163
997	1170
998	1208
999	1188
1000	12158999