1	391826199
2	36831168
3	11219617
4	5049737
5	2667664
6	1477539
7	897764
8	551313
9	366753
10	248917
11	178168
12	134517
13	104321
14	82581
15	68001
16	60228
17	57435
18	59529
19	64204
20	72605
21	91684
22	120733
23	161894
24	204908
25	260988
26	329511
27	394409
28	456034
29	509597
30	543722
31	578276
32	592412
33	609237
34	601372
35	575798
36	528214
37	497698
38	458220
39	417105
40	387255
41	377812
42	388374
43	433020
44	505686
45	602781
46	757891
47	963961
48	1228347
49	1558965
50	1967568
51	2454184
52	3013703
53	3622433
54	4307076
55	5035188
56	5863539
57	6664984
58	7492777
59	8344223
60	9168151
61	9951019
62	10650999
63	11170140
64	11559542
65	11760615
66	11816351
67	11687471
68	11439078
69	11065571
70	10541380
71	9907313
72	9228946
73	8456892
74	7677416
75	6865885
76	6090956
77	5346720
78	4634652
79	3976709
80	3360482
81	2791901
82	2333985
83	1923739
84	1565038
85	1261174
86	1024599
87	818860
88	653521
89	511420
90	392279
91	300577
92	229114
93	172286
94	133873
95	107157
96	89046
97	75655
98	66201
99	58756
100	53527
101	48482
102	45555
103	42478
104	41202
105	40891
106	41251
107	42782
108	43305
109	43889
110	45863
111	48421
112	49312
113	51382
114	51185
115	53246
116	53921
117	56072
118	57896
119	60507
120	62081
121	64778
122	65557
123	67705
124	70341
125	73896
126	76346
127	77254
128	77552
129	79640
130	80537
131	79668
132	78597
133	78363
134	75407
135	75271
136	72690
137	69804
138	66357
139	64436
140	61988
141	57532
142	54667
143	51866
144	48621
145	43654
146	40815
147	37600
148	35240
149	32306
150	29806
151	27109
152	25109
153	23589
154	21978
155	19797
156	19096
157	18237
158	16693
159	15884
160	14214
161	13224
162	12541
163	12206
164	11812
165	12437
166	12437
167	12284
168	12329
169	12212
170	11964
171	12407
172	12926
173	13557
174	13636
175	13516
176	14192
177	14534
178	14541
179	15207
180	15467
181	16095
182	16867
183	17360
184	17466
185	18071
186	19062
187	19912
188	21114
189	21817
190	21658
191	21958
192	23127
193	23214
194	22478
195	22540
196	22340
197	22076
198	21976
199	22364
200	22107
201	21439
202	20837
203	20360
204	19771
205	18796
206	18471
207	18454
208	17656
209	17183
210	16249
211	15639
212	15712
213	15012
214	14372
215	14087
216	13605
217	12864
218	12409
219	11760
220	10671
221	10035
222	9827
223	9064
224	8696
225	8268
226	7910
227	7734
228	7877
229	7607
230	7757
231	7716
232	7435
233	7401
234	7234
235	7229
236	7474
237	7403
238	7603
239	7481
240	7907
241	7884
242	8066
243	8571
244	8659
245	8942
246	9158
247	9092
248	8986
249	9358
250	9956
251	9891
252	10187
253	10367
254	10959
255	11037
256	11140
257	11161
258	10987
259	11189
260	11823
261	11770
262	12071
263	11715
264	11861
265	11493
266	11735
267	12131
268	11658
269	11440
270	10821
271	10723
272	10021
273	9975
274	9755
275	9510
276	9207
277	8700
278	8567
279	8065
280	7835
281	7536
282	7025
283	6742
284	6675
285	6368
286	6518
287	6190
288	5933
289	5684
290	5644
291	5714
292	5572
293	5923
294	5881
295	6116
296	6096
297	6291
298	6260
299	6222
300	6127
301	6174
302	6117
303	6036
304	5602
305	5727
306	6180
307	6079
308	6027
309	6180
310	5849
311	5949
312	5818
313	5771
314	5778
315	6126
316	6177
317	6521
318	6700
319	6793
320	6682
321	6818
322	6664
323	6493
324	6771
325	6281
326	6512
327	6466
328	6524
329	6553
330	6601
331	6480
332	6541
333	6549
334	6511
335	6429
336	6570
337	6459
338	6307
339	6527
340	6722
341	6465
342	6373
343	6081
344	5971
345	5826
346	5956
347	6037
348	5834
349	5845
350	6031
351	5973
352	5901
353	5576
354	6095
355	6169
356	6043
357	6079
358	6036
359	6081
360	6186
361	6248
362	6479
363	6889
364	7111
365	7185
366	7683
367	8335
368	8694
369	9312
370	10055
371	10168
372	11011
373	11725
374	11975
375	12959
376	13870
377	14621
378	14705
379	14953
380	15658
381	16493
382	17715
383	18551
384	19295
385	19598
386	20884
387	21974
388	22723
389	23340
390	23844
391	23819
392	23775
393	24481
394	25586
395	26085
396	26760
397	26876
398	26773
399	26714
400	27254
401	27649
402	28248
403	27411
404	26881
405	25926
406	25906
407	26264
408	26089
409	25790
410	25880
411	25774
412	25347
413	24434
414	24205
415	23529
416	22803
417	22109
418	21650
419	21445
420	21132
421	20620
422	20128
423	19321
424	19023
425	17950
426	17297
427	17044
428	16418
429	15490
430	15002
431	14127
432	14340
433	14140
434	13797
435	13423
436	12914
437	13139
438	12712
439	11690
440	11958
441	11457
442	10935
443	10240
444	9509
445	8980
446	8522
447	7473
448	7349
449	6952
450	6541
451	6375
452	6432
453	5775
454	5620
455	5409
456	5238
457	5274
458	5075
459	4991
460	4559
461	4598
462	4614
463	4589
464	4498
465	4516
466	4226
467	4202
468	4480
469	4339
470	4129
471	3987
472	4091
473	4180
474	4017
475	4093
476	4146
477	3979
478	3856
479	3746
480	4033
481	4185
482	4072
483	3944
484	3855
485	3754
486	3690
487	3742
488	3619
489	3640
490	3654
491	3554
492	3652
493	3456
494	3518
495	3498
496	3567
497	3454
498	3510
499	3522
500	3649
501	3577
502	3330
503	3225
504	3293
505	3174
506	3235
507	3098
508	3061
509	3104
510	3029
511	3003
512	2974
513	2810
514	2946
515	2763
516	2674
517	2649
518	2577
519	2520
520	2719
521	2656
522	2613
523	2558
524	2552
525	2672
526	2628
527	2465
528	2474
529	2401
530	2407
531	2513
532	2563
533	2317
534	2476
535	2348
536	2361
537	2421
538	2355
539	2364
540	2277
541	2244
542	2142
543	2146
544	2073
545	2025
546	2176
547	2093
548	2031
549	2303
550	2076
551	2062
552	2113
553	2173
554	2144
555	2093
556	2027
557	2019
558	2039
559	1968
560	1979
561	2080
562	1921
563	2006
564	1958
565	1912
566	1931
567	1865
568	1856
569	1835
570	1880
571	1839
572	1828
573	1764
574	1808
575	1788
576	1871
577	1787
578	1727
579	1637
580	1620
581	1701
582	1635
583	1747
584	1656
585	1729
586	1793
587	1696
588	1671
589	1563
590	1557
591	1546
592	1603
593	1555
594	1534
595	1558
596	1623
597	1630
598	1624
599	1586
600	1580
601	1559
602	1560
603	1569
604	1537
605	1431
606	1466
607	1488
608	1498
609	1447
610	1455
611	1446
612	1511
613	1488
614	1499
615	1584
616	1546
617	1575
618	1583
619	1488
620	1456
621	1512
622	1499
623	1460
624	1525
625	1576
626	1585
627	1604
628	1552
629	1566
630	1579
631	1715
632	1687
633	1638
634	1524
635	1507
636	1516
637	1492
638	1476
639	1397
640	1422
641	1516
642	1337
643	1423
644	1566
645	1455
646	1422
647	1393
648	1401
649	1381
650	1352
651	1443
652	1411
653	1351
654	1415
655	1324
656	1356
657	1373
658	1430
659	1266
660	1392
661	1356
662	1386
663	1348
664	1320
665	1365
666	1442
667	1423
668	1293
669	1284
670	1299
671	1313
672	1401
673	1441
674	1421
675	1283
676	1396
677	1304
678	1362
679	1326
680	1298
681	1253
682	1249
683	1305
684	1296
685	1302
686	1277
687	1249
688	1446
689	1406
690	1367
691	1358
692	1354
693	1366
694	1411
695	1308
696	1340
697	1272
698	1324
699	1307
700	1247
701	1245
702	1147
703	1175
704	1143
705	1178
706	1160
707	1110
708	1139
709	1146
710	1129
711	1140
712	1084
713	1087
714	1122
715	1055
716	1092
717	1100
718	1099
719	1153
720	1094
721	1156
722	1099
723	1026
724	1023
725	1002
726	1061
727	1128
728	1151
729	1131
730	1153
731	1132
732	1188
733	977
734	991
735	1057
736	1018
737	1010
738	999
739	948
740	974
741	1100
742	1082
743	1132
744	1122
745	1024
746	969
747	989
748	973
749	914
750	977
751	1090
752	1053
753	1104
754	1069
755	1099
756	1110
757	1164
758	1082
759	1075
760	1223
761	1191
762	1174
763	1165
764	1092
765	1161
766	1071
767	1113
768	1102
769	1111
770	1094
771	1081
772	1147
773	1117
774	1162
775	1133
776	1086
777	1052
778	1075
779	1123
780	1040
781	1077
782	1066
783	1107
784	1145
785	1127
786	1092
787	1010
788	1038
789	1119
790	1170
791	1243
792	1255
793	1255
794	1193
795	1236
796	1144
797	1229
798	1161
799	1104
800	1176
801	1119
802	1141
803	1067
804	1110
805	1061
806	1007
807	1027
808	1075
809	1112
810	1061
811	994
812	1079
813	1051
814	958
815	1065
816	1022
817	1031
818	974
819	960
820	961
821	922
822	902
823	1022
824	939
825	975
826	920
827	907
828	984
829	871
830	931
831	943
832	1003
833	908
834	910
835	972
836	936
837	916
838	974
839	969
840	964
841	939
842	953
843	961
844	923
845	864
846	846
847	844
848	797
849	830
850	764
851	827
852	876
853	839
854	880
855	800
856	724
857	826
858	786
859	771
860	793
861	773
862	747
863	794
864	764
865	793
866	727
867	714
868	751
869	704
870	773
871	782
872	719
873	744
874	763
875	776
876	785
877	798
878	779
879	818
880	771
881	746
882	761
883	795
884	784
885	756
886	731
887	792
888	717
889	741
890	726
891	674
892	734
893	696
894	716
895	687
896	778
897	693
898	683
899	727
900	754
901	704
902	725
903	701
904	721
905	703
906	693
907	770
908	737
909	717
910	718
911	759
912	722
913	749
914	751
915	727
916	744
917	710
918	723
919	696
920	727
921	758
922	812
923	739
924	713
925	647
926	695
927	704
928	651
929	658
930	686
931	640
932	694
933	741
934	729
935	673
936	671
937	652
938	642
939	620
940	609
941	589
942	580
943	662
944	619
945	641
946	641
947	650
948	658
949	635
950	629
951	619
952	552
953	628
954	611
955	606
956	535
957	545
958	534
959	540
960	522
961	465
962	528
963	546
964	548
965	539
966	542
967	465
968	497
969	602
970	522
971	503
972	502
973	483
974	488
975	547
976	533
977	496
978	541
979	517
980	542
981	507
982	533
983	570
984	553
985	605
986	554
987	512
988	490
989	536
990	548
991	555
992	527
993	547
994	544
995	496
996	526
997	489
998	526
999	494
1000	2353873