1	1224228672
2	123189553
3	34290672
4	14306793
5	7552282
6	4800510
7	3653935
8	3369889
9	3667437
10	4379977
11	5533800
12	7040087
13	8926140
14	11161498
15	13795364
16	16794233
17	20017241
18	23299516
19	26537137
20	29650906
21	32343647
22	34750390
23	36552599
24	37717148
25	38165323
26	37876773
27	37029465
28	35581948
29	33633842
30	31298938
31	28706351
32	25962509
33	23092383
34	20351560
35	17714629
36	15331288
37	13371339
38	11710515
39	10374573
40	9292026
41	8463734
42	7844116
43	7415350
44	7158413
45	7032671
46	6973571
47	6997273
48	7038774
49	7103898
50	7132369
51	7170790
52	7159902
53	7138153
54	7082171
55	7008582
56	6869409
57	6712679
58	6504325
59	6251020
60	5997089
61	5711570
62	5375998
63	5029720
64	4673654
65	4309845
66	3997019
67	3656945
68	3323415
69	2996573
70	2693204
71	2417179
72	2149650
73	1906215
74	1699797
75	1508107
76	1339357
77	1193905
78	1063539
79	954443
80	863128
81	779006
82	705629
83	647595
84	597831
85	553757
86	522381
87	489531
88	464179
89	442109
90	421631
91	402395
92	387632
93	370670
94	361465
95	352106
96	341633
97	334674
98	326681
99	319102
100	312557
101	302605
102	295349
103	289394
104	281813
105	273568
106	267731
107	262921
108	258779
109	252473
110	246178
111	241569
112	235684
113	231387
114	227413
115	223303
116	220382
117	216104
118	210708
119	207518
120	201393
121	196741
122	194431
123	190111
124	186201
125	182434
126	179048
127	175079
128	168708
129	165171
130	161004
131	156587
132	152968
133	148742
134	144979
135	142126
136	138508
137	135943
138	132719
139	130311
140	126237
141	123605
142	121823
143	120873
144	117389
145	114167
146	110111
147	108924
148	106937
149	103573
150	101286
151	99459
152	97838
153	97932
154	96197
155	93368
156	91938
157	91218
158	90003
159	88817
160	86418
161	85594
162	83982
163	82407
164	80079
165	80059
166	78621
167	78447
168	77042
169	75501
170	74450
171	74963
172	75120
173	73831
174	74124
175	71739
176	71404
177	71884
178	70161
179	68677
180	68144
181	66020
182	66424
183	66024
184	65412
185	64439
186	63038
187	61249
188	60370
189	60670
190	60374
191	59817
192	57734
193	56877
194	56293
195	55610
196	54933
197	53394
198	53078
199	52127
200	51329
201	50923
202	50812
203	50030
204	50078
205	49082
206	49254
207	47769
208	47915
209	47708
210	46522
211	45454
212	45062
213	44416
214	44012
215	44519
216	42651
217	42846
218	42934
219	41769
220	41863
221	41788
222	41128
223	40542
224	40569
225	40195
226	39711
227	39426
228	39344
229	38370
230	39302
231	38538
232	37855
233	38112
234	37272
235	37256
236	36475
237	36316
238	35971
239	35486
240	34548
241	34127
242	33833
243	33431
244	33319
245	32949
246	32442
247	32619
248	31582
249	30976
250	30411
251	30381
252	30581
253	30609
254	30314
255	29691
256	29953
257	30054
258	30600
259	29807
260	29457
261	28892
262	28469
263	28818
264	28650
265	28060
266	27658
267	27148
268	27165
269	26825
270	25469
271	25723
272	25799
273	25639
274	25718
275	25566
276	25507
277	25749
278	25233
279	24299
280	24552
281	24144
282	24266
283	23707
284	23481
285	23654
286	22819
287	22589
288	22561
289	22527
290	22027
291	22366
292	21991
293	21782
294	21750
295	21472
296	21644
297	21398
298	21385
299	20711
300	20571
301	20920
302	20721
303	20603
304	20443
305	19869
306	20008
307	20037
308	19525
309	19640
310	19683
311	19472
312	18913
313	18784
314	18619
315	18701
316	18638
317	18615
318	18744
319	18604
320	18210
321	18144
322	18058
323	18073
324	18241
325	18092
326	17415
327	17605
328	17497
329	16995
330	16871
331	17150
332	16911
333	16675
334	16954
335	16707
336	16569
337	16789
338	16681
339	16676
340	16643
341	16428
342	16442
343	16334
344	16224
345	15902
346	15937
347	15592
348	15271
349	15340
350	15620
351	15387
352	15059
353	15161
354	15105
355	14549
356	14264
357	13891
358	14122
359	13790
360	13790
361	13998
362	13469
363	13537
364	13440
365	13384
366	13282
367	13071
368	13503
369	13149
370	13007
371	13261
372	13051
373	12738
374	12481
375	12678
376	12690
377	12421
378	12022
379	11912
380	12152
381	12091
382	11855
383	11891
384	11619
385	12041
386	11603
387	11842
388	11619
389	11649
390	11612
391	11432
392	10943
393	11074
394	11354
395	11115
396	11209
397	10945
398	10889
399	10618
400	10719
401	10715
402	10704
403	10478
404	10528
405	10324
406	10332
407	10211
408	10470
409	10257
410	10278
411	10123
412	9949
413	10094
414	9906
415	9913
416	9827
417	9870
418	9602
419	9784
420	9738
421	9899
422	9799
423	9386
424	9359
425	9429
426	9443
427	9494
428	9360
429	9496
430	9321
431	9405
432	9226
433	9285
434	9059
435	9089
436	9056
437	9324
438	8805
439	8790
440	8760
441	8550
442	8654
443	8552
444	8561
445	8669
446	8512
447	8217
448	8174
449	8095
450	8251
451	8382
452	8276
453	8330
454	8436
455	8329
456	8297
457	8168
458	8251
459	8344
460	8076
461	8218
462	8108
463	7956
464	7759
465	7833
466	7888
467	7673
468	7709
469	7771
470	7813
471	7718
472	7517
473	7428
474	7503
475	7537
476	7475
477	7261
478	7240
479	7186
480	7179
481	7087
482	7181
483	7183
484	7131
485	7067
486	6957
487	6761
488	6674
489	6777
490	6788
491	6880
492	6849
493	6692
494	6644
495	6712
496	6702
497	6483
498	6581
499	6501
500	6357
501	6552
502	6410
503	6251
504	6514
505	6288
506	6242
507	6301
508	6238
509	6162
510	6381
511	6315
512	6323
513	6184
514	6082
515	6179
516	5975
517	6018
518	5891
519	5897
520	5819
521	5911
522	5910
523	5826
524	5832
525	5937
526	5927
527	5951
528	5829
529	6019
530	5752
531	5773
532	5674
533	5899
534	5631
535	5643
536	5610
537	5640
538	5548
539	5364
540	5366
541	5301
542	5267
543	5306
544	5334
545	5364
546	5304
547	5491
548	5353
549	5037
550	5159
551	5163
552	5237
553	5050
554	5083
555	5021
556	5003
557	4987
558	5037
559	4857
560	4832
561	4990
562	4944
563	4817
564	5050
565	4877
566	4869
567	4947
568	4783
569	4927
570	4769
571	4723
572	4760
573	4871
574	4766
575	4501
576	4534
577	4593
578	4642
579	4513
580	4603
581	4506
582	4596
583	4412
584	4642
585	4359
586	4334
587	4490
588	4518
589	4430
590	4526
591	4393
592	4439
593	4415
594	4456
595	4373
596	4177
597	4246
598	4290
599	4257
600	4460
601	4227
602	4263
603	4138
604	4197
605	4132
606	4226
607	4223
608	4142
609	4193
610	4050
611	4179
612	4258
613	4308
614	4076
615	4030
616	3945
617	4013
618	3966
619	4086
620	3916
621	4050
622	3814
623	3856
624	3676
625	3836
626	3734
627	3796
628	3764
629	3812
630	3662
631	3802
632	3673
633	3772
634	3785
635	3726
636	3659
637	3616
638	3649
639	3657
640	3515
641	3563
642	3413
643	3268
644	3455
645	3464
646	3489
647	3477
648	3445
649	3546
650	3507
651	3442
652	3461
653	3454
654	3404
655	3327
656	3361
657	3396
658	3301
659	3397
660	3456
661	3170
662	3264
663	3186
664	3198
665	3124
666	3176
667	3196
668	3208
669	3111
670	3012
671	3116
672	3154
673	3136
674	3059
675	3085
676	3101
677	3208
678	3174
679	3219
680	3159
681	3079
682	3040
683	3143
684	3020
685	3083
686	3384
687	3137
688	3077
689	3102
690	2927
691	2979
692	2990
693	2911
694	3013
695	3032
696	2928
697	3003
698	2936
699	2856
700	2925
701	3017
702	2909
703	2883
704	2972
705	2859
706	2857
707	3021
708	2859
709	2935
710	2852
711	3068
712	2827
713	2991
714	2926
715	3020
716	2941
717	2800
718	2884
719	2932
720	2751
721	2925
722	2869
723	2885
724	2723
725	2670
726	2743
727	2780
728	2835
729	2795
730	2782
731	2796
732	2807
733	2812
734	2828
735	2773
736	2766
737	2638
738	2719
739	2653
740	2733
741	2534
742	2629
743	2647
744	2687
745	2696
746	2758
747	2642
748	2670
749	2536
750	2466
751	2523
752	2385
753	2481
754	2514
755	2455
756	2524
757	2513
758	2626
759	2612
760	2454
761	2378
762	2344
763	2323
764	2448
765	2453
766	2486
767	2461
768	2409
769	2367
770	2433
771	2436
772	2478
773	2496
774	2496
775	2499
776	2382
777	2294
778	2237
779	2356
780	2321
781	2335
782	2289
783	2389
784	2305
785	2241
786	2261
787	2394
788	2216
789	2210
790	2252
791	2245
792	2167
793	2147
794	2255
795	2162
796	2121
797	2104
798	2240
799	2204
800	2158
801	2189
802	2133
803	2038
804	2165
805	2198
806	2073
807	2139
808	2173
809	2050
810	2123
811	2156
812	2085
813	2076
814	2084
815	2083
816	2115
817	2104
818	2099
819	2067
820	2042
821	2093
822	1976
823	2037
824	2083
825	2069
826	1995
827	1933
828	1954
829	1917
830	1951
831	1949
832	1978
833	1967
834	1968
835	1903
836	1913
837	1858
838	1926
839	1853
840	1925
841	1919
842	1949
843	1849
844	1921
845	1819
846	1860
847	1873
848	1898
849	1841
850	1753
851	1825
852	1678
853	1821
854	1876
855	1920
856	1785
857	1860
858	1871
859	1762
860	1840
861	1774
862	1854
863	1741
864	1855
865	1822
866	1767
867	1768
868	1835
869	1734
870	1695
871	1748
872	1721
873	1719
874	1734
875	1775
876	1710
877	1733
878	1661
879	1622
880	1743
881	1750
882	1659
883	1691
884	1670
885	1697
886	1715
887	1770
888	1737
889	1712
890	1606
891	1694
892	1665
893	1723
894	1675
895	1667
896	1692
897	1659
898	1631
899	1683
900	1642
901	1531
902	1620
903	1570
904	1618
905	1615
906	1621
907	1617
908	1515
909	1487
910	1494
911	1535
912	1514
913	1589
914	1475
915	1505
916	1470
917	1532
918	1580
919	1578
920	1514
921	1492
922	1613
923	1558
924	1560
925	1546
926	1673
927	1549
928	1522
929	1458
930	1486
931	1505
932	1428
933	1457
934	1449
935	1480
936	1474
937	1389
938	1436
939	1572
940	1509
941	1456
942	1417
943	1474
944	1470
945	1420
946	1410
947	1486
948	1463
949	1456
950	1447
951	1416
952	1523
953	1418
954	1411
955	1426
956	1388
957	1411
958	1358
959	1382
960	1360
961	1494
962	1454
963	1460
964	1395
965	1447
966	1376
967	1374
968	1415
969	1416
970	1439
971	1327
972	1358
973	1349
974	1321
975	1381
976	1297
977	1398
978	1318
979	1303
980	1304
981	1304
982	1309
983	1299
984	1370
985	1383
986	1331
987	1291
988	1284
989	1318
990	1304
991	1274
992	1294
993	1286
994	1269
995	1307
996	1248
997	1350
998	1315
999	1329
1000	9661468