1	565570224
2	69010449
3	20586535
4	8597529
5	4412887
6	2616170
7	1733712
8	1254516
9	966485
10	788294
11	682185
12	624295
13	607306
14	627943
15	698745
16	800172
17	938888
18	1103859
19	1295554
20	1500052
21	1719338
22	1897968
23	2047268
24	2160580
25	2263926
26	2302923
27	2299707
28	2258372
29	2199886
30	2141652
31	2065295
32	2004325
33	1984468
34	2006076
35	2091892
36	2228169
37	2466547
38	2796945
39	3164933
40	3632109
41	4168695
42	4781728
43	5427768
44	6106535
45	6823373
46	7529408
47	8197261
48	8812200
49	9314535
50	9751587
51	10064569
52	10286746
53	10356284
54	10299006
55	10125473
56	9785376
57	9352990
58	8856158
59	8265173
60	7647276
61	6968903
62	6271824
63	5600118
64	4931803
65	4292425
66	3668850
67	3106235
68	2612725
69	2181725
70	1797279
71	1473224
72	1188230
73	966846
74	785034
75	639020
76	514774
77	422698
78	355217
79	300420
80	255588
81	224396
82	203463
83	184662
84	175423
85	170898
86	169162
87	170361
88	170518
89	169506
90	173677
91	177993
92	181676
93	186379
94	192986
95	197689
96	201736
97	205729
98	208745
99	213605
100	219534
101	221595
102	223283
103	225607
104	226605
105	226175
106	224281
107	224007
108	219998
109	218045
110	213741
111	210931
112	203778
113	198781
114	193618
115	186667
116	180612
117	173385
118	163501
119	156528
120	149988
121	144648
122	136965
123	130537
124	124220
125	118658
126	115785
127	112031
128	105603
129	101529
130	97600
131	93358
132	89559
133	86683
134	85951
135	81913
136	80552
137	79232
138	78040
139	76705
140	75713
141	74795
142	74193
143	74516
144	75870
145	76400
146	77521
147	77524
148	77788
149	78213
150	78627
151	80351
152	80381
153	79608
154	80433
155	80005
156	81417
157	82106
158	81054
159	80343
160	77837
161	78698
162	77804
163	76361
164	76549
165	73599
166	73661
167	72389
168	71142
169	69604
170	67901
171	68494
172	67712
173	65779
174	65817
175	64292
176	63102
177	62208
178	59294
179	58987
180	58632
181	56708
182	56300
183	54550
184	53882
185	52304
186	51034
187	50448
188	48833
189	46923
190	46361
191	45950
192	46195
193	45504
194	45332
195	45093
196	44438
197	44694
198	44513
199	44576
200	44546
201	44692
202	44400
203	44352
204	44108
205	43439
206	43827
207	43158
208	43500
209	44517
210	44319
211	44861
212	44673
213	44450
214	44249
215	43090
216	43311
217	43074
218	42962
219	42611
220	42298
221	41310
222	41314
223	40971
224	41056
225	40945
226	40270
227	39099
228	39142
229	38291
230	37732
231	36751
232	36549
233	35892
234	36525
235	34634
236	34213
237	33926
238	33273
239	32810
240	32468
241	32616
242	31993
243	30793
244	30725
245	30919
246	29953
247	30204
248	29191
249	28432
250	28099
251	28259
252	27588
253	27581
254	27679
255	27096
256	27377
257	27283
258	26083
259	26565
260	26922
261	27439
262	27431
263	26566
264	26411
265	26122
266	25840
267	26073
268	26281
269	25127
270	25346
271	25389
272	25284
273	25152
274	24904
275	25047
276	24601
277	24490
278	24232
279	23930
280	23852
281	23688
282	23407
283	23370
284	22982
285	22831
286	22537
287	21731
288	22003
289	21816
290	21566
291	21120
292	20848
293	20463
294	19910
295	19867
296	19833
297	19734
298	19862
299	19568
300	19347
301	19360
302	19250
303	19425
304	19214
305	19180
306	18927
307	18808
308	18161
309	18488
310	18498
311	18562
312	18223
313	18117
314	17851
315	17438
316	17454
317	17319
318	17312
319	17193
320	17474
321	17326
322	16951
323	16937
324	17114
325	17226
326	16731
327	16747
328	17013
329	16166
330	16386
331	16017
332	15657
333	16142
334	15742
335	15523
336	15409
337	15571
338	15725
339	15645
340	15409
341	15653
342	15643
343	15205
344	15229
345	15491
346	14717
347	14360
348	14431
349	14318
350	13677
351	13907
352	13741
353	14150
354	13849
355	14073
356	13875
357	13531
358	13539
359	13163
360	13469
361	13305
362	12868
363	12569
364	12559
365	12567
366	12156
367	12419
368	12040
369	11674
370	11996
371	12165
372	12027
373	11828
374	12095
375	11507
376	12076
377	11808
378	11679
379	11595
380	11408
381	11524
382	11485
383	11252
384	11611
385	11605
386	11515
387	11610
388	11495
389	10954
390	11363
391	11612
392	11904
393	11828
394	11713
395	11668
396	11647
397	11287
398	11632
399	11258
400	11026
401	11183
402	10939
403	10890
404	10878
405	10806
406	10838
407	10535
408	10228
409	9856
410	9868
411	10202
412	9757
413	9937
414	9702
415	9982
416	9532
417	9562
418	9431
419	9244
420	9112
421	9044
422	8825
423	8871
424	8875
425	8864
426	8993
427	8773
428	8403
429	8555
430	8308
431	8401
432	8251
433	8320
434	8336
435	8342
436	8408
437	8345
438	8209
439	8327
440	8077
441	8256
442	8314
443	8193
444	8152
445	8249
446	8118
447	8022
448	8334
449	8124
450	8061
451	7993
452	7789
453	7811
454	7881
455	8097
456	7744
457	8017
458	7934
459	7642
460	7606
461	7825
462	7592
463	7644
464	7475
465	7559
466	7264
467	7221
468	7091
469	7226
470	7258
471	7082
472	6897
473	6691
474	6690
475	6953
476	6959
477	6559
478	6818
479	6637
480	6612
481	6721
482	6660
483	6371
484	6525
485	6275
486	6193
487	6204
488	6130
489	6247
490	6239
491	5938
492	5903
493	5728
494	5904
495	5993
496	5792
497	5850
498	5545
499	5697
500	5618
501	5711
502	5637
503	5606
504	5640
505	5428
506	5487
507	5598
508	5323
509	5198
510	5372
511	5200
512	5341
513	4992
514	5178
515	5267
516	5103
517	5135
518	5234
519	5184
520	5156
521	4936
522	4951
523	5100
524	5099
525	5162
526	5078
527	4956
528	4930
529	5025
530	4914
531	4949
532	4684
533	4697
534	4789
535	4581
536	4631
537	4481
538	4336
539	4341
540	4399
541	4477
542	4283
543	4347
544	4263
545	4257
546	3992
547	4194
548	3912
549	4174
550	4100
551	4219
552	4087
553	4203
554	4066
555	4249
556	4134
557	4129
558	4122
559	4224
560	4100
561	3985
562	4054
563	4032
564	3995
565	3984
566	3833
567	3842
568	3728
569	3797
570	3784
571	3905
572	3850
573	3885
574	3929
575	4022
576	3975
577	3906
578	3935
579	3761
580	3800
581	3724
582	3815
583	3601
584	3583
585	3617
586	3580
587	3671
588	3606
589	3559
590	3614
591	3523
592	3530
593	3472
594	3504
595	3460
596	3431
597	3338
598	3485
599	3321
600	3382
601	3417
602	3344
603	3365
604	3342
605	3233
606	3358
607	3350
608	3371
609	3134
610	3221
611	3220
612	3273
613	3088
614	3231
615	3267
616	3290
617	3257
618	3240
619	3237
620	3221
621	3338
622	3182
623	3184
624	3101
625	3034
626	3006
627	3233
628	2885
629	2823
630	3078
631	2980
632	2933
633	3012
634	2838
635	2917
636	2955
637	2818
638	2818
639	2946
640	2922
641	2862
642	2893
643	2880
644	2948
645	2847
646	2845
647	2793
648	2967
649	2817
650	2810
651	2738
652	2883
653	2651
654	2790
655	2709
656	2796
657	2779
658	2837
659	2835
660	2748
661	2640
662	2652
663	2717
664	2726
665	2666
666	2517
667	2619
668	2584
669	2587
670	2548
671	2645
672	2472
673	2664
674	2678
675	2534
676	2613
677	2589
678	2513
679	2438
680	2419
681	2544
682	2415
683	2536
684	2432
685	2546
686	2505
687	2418
688	2491
689	2440
690	2316
691	2384
692	2377
693	2346
694	2434
695	2389
696	2440
697	2427
698	2401
699	2372
700	2384
701	2330
702	2364
703	2432
704	2473
705	2320
706	2367
707	2279
708	2142
709	2262
710	2354
711	2324
712	2253
713	2219
714	2231
715	2253
716	2270
717	2329
718	2185
719	2251
720	2194
721	2251
722	2089
723	2079
724	2213
725	2179
726	2104
727	2185
728	2266
729	2348
730	2192
731	2214
732	2166
733	2138
734	2074
735	2149
736	2171
737	2111
738	2202
739	2090
740	2138
741	2143
742	2122
743	2162
744	2054
745	2181
746	2054
747	1989
748	1996
749	2037
750	1992
751	2010
752	1967
753	1891
754	1914
755	1932
756	2061
757	2074
758	1943
759	2004
760	2000
761	1940
762	1900
763	1904
764	1872
765	1891
766	1854
767	1945
768	1904
769	1983
770	1843
771	1974
772	1906
773	1903
774	1979
775	1851
776	1886
777	1793
778	1870
779	1956
780	1828
781	1759
782	1805
783	1865
784	1868
785	1785
786	1820
787	1757
788	1877
789	1874
790	1805
791	1815
792	1888
793	1839
794	1797
795	1764
796	1733
797	1726
798	1867
799	1823
800	1827
801	1764
802	1768
803	1780
804	1742
805	1783
806	1690
807	1741
808	1662
809	1677
810	1733
811	1819
812	1783
813	1732
814	1815
815	1672
816	1836
817	1794
818	1804
819	1712
820	1657
821	1702
822	1732
823	1635
824	1652
825	1667
826	1570
827	1706
828	1586
829	1688
830	1739
831	1639
832	1648
833	1677
834	1750
835	1691
836	1737
837	1717
838	1617
839	1574
840	1645
841	1661
842	1718
843	1655
844	1554
845	1580
846	1577
847	1650
848	1683
849	1600
850	1587
851	1551
852	1595
853	1415
854	1565
855	1489
856	1582
857	1572
858	1482
859	1452
860	1469
861	1534
862	1595
863	1457
864	1501
865	1410
866	1523
867	1487
868	1460
869	1500
870	1397
871	1384
872	1283
873	1312
874	1490
875	1346
876	1454
877	1432
878	1362
879	1398
880	1296
881	1386
882	1377
883	1365
884	1444
885	1352
886	1334
887	1351
888	1381
889	1375
890	1349
891	1331
892	1435
893	1299
894	1358
895	1382
896	1317
897	1343
898	1347
899	1467
900	1352
901	1324
902	1254
903	1337
904	1237
905	1338
906	1322
907	1213
908	1256
909	1287
910	1280
911	1262
912	1204
913	1247
914	1275
915	1237
916	1184
917	1257
918	1216
919	1263
920	1288
921	1204
922	1274
923	1254
924	1261
925	1214
926	1179
927	1218
928	1166
929	1216
930	1228
931	1148
932	1185
933	1184
934	1252
935	1279
936	1167
937	1170
938	1151
939	1160
940	1157
941	1178
942	1186
943	1133
944	1110
945	1181
946	1209
947	1165
948	1147
949	1162
950	1168
951	1138
952	1203
953	1137
954	1265
955	1166
956	1204
957	1231
958	1335
959	1163
960	1125
961	1167
962	1115
963	1161
964	1109
965	1170
966	1145
967	1089
968	1210
969	1228
970	1174
971	1196
972	1160
973	1217
974	1094
975	1119
976	1162
977	1073
978	1140
979	1108
980	1064
981	1081
982	1064
983	1116
984	1185
985	1065
986	1102
987	1127
988	1071
989	1059
990	1107
991	1112
992	1163
993	1166
994	1112
995	1097
996	1064
997	1092
998	1112
999	1091
1000	7823524