1	693624192
2	59392332
3	20266762
4	14069476
5	13790135
6	15988255
7	19055101
8	23076970
9	27527763
10	31628994
11	35134341
12	37517976
13	38786678
14	38979072
15	38233904
16	36438777
17	34208765
18	31607310
19	28811918
20	26176983
21	23746035
22	21720443
23	20087437
24	18835414
25	17880753
26	17196312
27	16554495
28	16131521
29	15673487
30	15225497
31	14735992
32	14218951
33	13585191
34	12836351
35	11959271
36	11024863
37	10102313
38	9192531
39	8211825
40	7282179
41	6397915
42	5554293
43	4760127
44	4080707
45	3454883
46	2952560
47	2502474
48	2116152
49	1792057
50	1532342
51	1322429
52	1157874
53	1025087
54	920708
55	828300
56	771495
57	724195
58	680074
59	643486
60	618436
61	591867
62	566102
63	535254
64	511069
65	488023
66	469418
67	452669
68	440300
69	423737
70	410497
71	393416
72	380171
73	363771
74	346375
75	332589
76	318502
77	308135
78	298175
79	288359
80	279052
81	267705
82	257181
83	247293
84	240370
85	233603
86	225783
87	219481
88	211427
89	204943
90	200956
91	195177
92	189784
93	186352
94	182379
95	178896
96	175917
97	170515
98	168702
99	164215
100	160434
101	157068
102	152145
103	150921
104	148604
105	146548
106	143294
107	140112
108	136051
109	133196
110	130696
111	130022
112	126482
113	122677
114	120656
115	118673
116	117850
117	117213
118	113587
119	111941
120	110911
121	107859
122	106581
123	104761
124	103986
125	101468
126	100474
127	98449
128	95883
129	93375
130	90425
131	89956
132	88569
133	85975
134	84079
135	83521
136	82760
137	81178
138	79272
139	78740
140	78700
141	77680
142	76556
143	75030
144	73744
145	74810
146	73723
147	72732
148	70638
149	70170
150	70481
151	69145
152	68350
153	66817
154	65940
155	65209
156	64801
157	64344
158	62557
159	60966
160	60478
161	58560
162	58139
163	57029
164	55882
165	56391
166	55574
167	54564
168	53224
169	52037
170	52050
171	50839
172	50761
173	49659
174	49779
175	48927
176	48018
177	48056
178	47741
179	45895
180	45081
181	44779
182	45141
183	43963
184	43516
185	42838
186	43014
187	42392
188	41402
189	40346
190	40701
191	39135
192	39257
193	38068
194	38113
195	38033
196	37403
197	37052
198	36589
199	35676
200	36009
201	34926
202	34986
203	35111
204	34312
205	33793
206	33110
207	33164
208	33141
209	32851
210	31936
211	32089
212	31881
213	31066
214	31164
215	30805
216	31057
217	29327
218	29542
219	29313
220	28855
221	29048
222	28582
223	28290
224	27848
225	26999
226	26854
227	27094
228	26693
229	26206
230	25885
231	26487
232	26094
233	25840
234	25432
235	25009
236	24269
237	24064
238	23566
239	23777
240	23670
241	23281
242	23452
243	23087
244	22748
245	22906
246	22389
247	22065
248	21751
249	21924
250	21466
251	21744
252	21348
253	21510
254	21510
255	21362
256	21266
257	21006
258	21051
259	21090
260	20492
261	20625
262	20084
263	19789
264	19851
265	19715
266	19404
267	19477
268	19300
269	18933
270	18692
271	18364
272	18523
273	18461
274	18477
275	18163
276	17927
277	17683
278	17265
279	17493
280	17082
281	16970
282	16814
283	16760
284	16809
285	16408
286	16357
287	16439
288	16488
289	15713
290	15931
291	16197
292	15911
293	15689
294	15389
295	15683
296	15422
297	15254
298	15512
299	15171
300	15138
301	14499
302	14769
303	14505
304	14548
305	14517
306	14255
307	14316
308	14021
309	13759
310	13630
311	13514
312	13360
313	13245
314	13359
315	13138
316	13183
317	13014
318	12466
319	12658
320	12627
321	12823
322	12300
323	12254
324	12353
325	12534
326	12528
327	12476
328	11949
329	12000
330	11953
331	11808
332	11834
333	11595
334	11257
335	11524
336	11378
337	11593
338	11285
339	11091
340	11362
341	10918
342	11039
343	10777
344	10706
345	10298
346	10384
347	10350
348	10685
349	10733
350	10328
351	10168
352	10066
353	9874
354	9955
355	9762
356	9644
357	9395
358	9514
359	9187
360	9305
361	8857
362	9362
363	9304
364	9161
365	9352
366	9175
367	9115
368	8954
369	9111
370	9203
371	8673
372	8719
373	8584
374	8503
375	8439
376	8403
377	8731
378	8483
379	8378
380	8499
381	8257
382	8179
383	8007
384	8094
385	8377
386	7931
387	8268
388	7785
389	7839
390	7692
391	7696
392	7623
393	7710
394	7454
395	7333
396	7598
397	7568
398	7501
399	7123
400	7210
401	7094
402	7334
403	7243
404	6990
405	6998
406	6989
407	7179
408	6846
409	7046
410	6754
411	6635
412	6917
413	6609
414	6615
415	6376
416	6553
417	6603
418	6446
419	6459
420	6644
421	6508
422	6345
423	6355
424	6285
425	6401
426	6257
427	6269
428	6050
429	6258
430	6186
431	6137
432	6087
433	5975
434	5911
435	6003
436	6077
437	5961
438	5784
439	5953
440	5880
441	5848
442	5611
443	5720
444	5585
445	5724
446	5715
447	5601
448	5408
449	5688
450	5562
451	5593
452	5394
453	5303
454	5469
455	5348
456	5365
457	5536
458	5402
459	5170
460	5354
461	5236
462	5293
463	5260
464	5068
465	5147
466	5220
467	5271
468	5123
469	4962
470	5169
471	5036
472	4920
473	4996
474	4889
475	4919
476	4895
477	4915
478	4837
479	4880
480	4802
481	4803
482	4758
483	4699
484	4552
485	4699
486	4444
487	4377
488	4411
489	4212
490	4330
491	4446
492	4371
493	4449
494	4347
495	4340
496	4335
497	4311
498	4342
499	4271
500	4263
501	4093
502	4088
503	4150
504	4027
505	4055
506	3902
507	3981
508	4050
509	4049
510	3896
511	3954
512	3988
513	3966
514	3974
515	4043
516	3911
517	3988
518	3926
519	3798
520	3826
521	3788
522	3868
523	3776
524	3691
525	3825
526	3717
527	3758
528	3910
529	3886
530	3835
531	3765
532	3677
533	3662
534	3660
535	3604
536	3721
537	3552
538	3689
539	3618
540	3474
541	3494
542	3525
543	3403
544	3463
545	3392
546	3473
547	3437
548	3361
549	3481
550	3281
551	3528
552	3416
553	3439
554	3327
555	3276
556	3199
557	3368
558	3267
559	3348
560	3247
561	3247
562	3342
563	3416
564	3447
565	3379
566	3335
567	3361
568	3336
569	3419
570	3278
571	3303
572	3195
573	3282
574	3213
575	3270
576	3105
577	3217
578	3183
579	3164
580	3312
581	3097
582	3085
583	3107
584	3155
585	3117
586	3134
587	3045
588	3075
589	3021
590	2999
591	2988
592	2947
593	3007
594	3014
595	3067
596	3039
597	3119
598	3051
599	2934
600	2985
601	2953
602	2706
603	2859
604	2854
605	2782
606	2963
607	2914
608	2747
609	2670
610	2865
611	2710
612	2684
613	2736
614	2658
615	2474
616	2595
617	2620
618	2676
619	2607
620	2576
621	2745
622	2578
623	2574
624	2653
625	2493
626	2665
627	2637
628	2566
629	2583
630	2489
631	2598
632	2546
633	2544
634	2511
635	2466
636	2419
637	2387
638	2518
639	2456
640	2323
641	2448
642	2540
643	2469
644	2394
645	2501
646	2463
647	2392
648	2435
649	2481
650	2520
651	2461
652	2368
653	2343
654	2460
655	2487
656	2378
657	2325
658	2356
659	2485
660	2430
661	2363
662	2339
663	2312
664	2393
665	2344
666	2313
667	2367
668	2338
669	2304
670	2245
671	2278
672	2213
673	2203
674	2318
675	2177
676	2194
677	2249
678	2196
679	2054
680	2153
681	2204
682	2202
683	2159
684	2171
685	2074
686	2172
687	2058
688	2101
689	2105
690	2113
691	2064
692	1971
693	2029
694	2001
695	1996
696	2033
697	1954
698	1991
699	2042
700	2075
701	2063
702	2081
703	2031
704	1974
705	1973
706	1918
707	1792
708	1981
709	1881
710	1914
711	1899
712	1863
713	1875
714	1933
715	1944
716	1833
717	1879
718	1854
719	1776
720	1761
721	1821
722	1902
723	1806
724	1785
725	1813
726	1825
727	1695
728	1818
729	1859
730	1700
731	1754
732	1788
733	1813
734	1838
735	1859
736	1836
737	1757
738	1779
739	1794
740	1764
741	1748
742	1777
743	1836
744	1760
745	1716
746	1839
747	1798
748	1861
749	1819
750	1846
751	1738
752	1692
753	1668
754	1830
755	1753
756	1597
757	1742
758	1695
759	1666
760	1697
761	1644
762	1725
763	1731
764	1671
765	1604
766	1662
767	1636
768	1714
769	1609
770	1709
771	1702
772	1635
773	1625
774	1526
775	1530
776	1588
777	1634
778	1633
779	1669
780	1621
781	1631
782	1645
783	1625
784	1556
785	1599
786	1573
787	1524
788	1526
789	1531
790	1484
791	1482
792	1557
793	1530
794	1534
795	1535
796	1576
797	1470
798	1580
799	1508
800	1510
801	1457
802	1403
803	1382
804	1432
805	1415
806	1420
807	1445
808	1454
809	1425
810	1409
811	1410
812	1450
813	1508
814	1481
815	1402
816	1417
817	1392
818	1370
819	1325
820	1333
821	1384
822	1449
823	1404
824	1300
825	1337
826	1360
827	1364
828	1386
829	1357
830	1386
831	1395
832	1322
833	1361
834	1359
835	1418
836	1302
837	1370
838	1366
839	1334
840	1344
841	1259
842	1275
843	1279
844	1312
845	1337
846	1318
847	1233
848	1286
849	1262
850	1273
851	1289
852	1347
853	1290
854	1188
855	1271
856	1189
857	1254
858	1252
859	1196
860	1237
861	1180
862	1227
863	1220
864	1276
865	1202
866	1240
867	1219
868	1188
869	1188
870	1170
871	1184
872	1154
873	1171
874	1153
875	1220
876	1108
877	1205
878	1090
879	1169
880	1175
881	1213
882	1172
883	1169
884	1150
885	1106
886	1131
887	1101
888	1135
889	1122
890	1198
891	1178
892	1079
893	1081
894	1172
895	1078
896	1083
897	1144
898	1067
899	1172
900	1146
901	1170
902	1099
903	1051
904	1069
905	1112
906	1022
907	1093
908	1134
909	1068
910	1093
911	1097
912	1065
913	1096
914	1045
915	1068
916	1118
917	1098
918	1098
919	1075
920	1106
921	1094
922	1043
923	1032
924	1053
925	1095
926	1153
927	1142
928	1013
929	1092
930	1090
931	1014
932	1058
933	1077
934	1024
935	1039
936	1057
937	1025
938	1066
939	1096
940	1027
941	1031
942	1058
943	1006
944	1015
945	1000
946	991
947	1001
948	1051
949	989
950	962
951	961
952	942
953	949
954	1010
955	996
956	1046
957	997
958	989
959	995
960	934
961	1013
962	1069
963	1032
964	964
965	997
966	1000
967	997
968	1040
969	977
970	946
971	949
972	1005
973	981
974	992
975	945
976	937
977	948
978	973
979	1019
980	937
981	939
982	1007
983	1034
984	1038
985	941
986	977
987	944
988	996
989	930
990	953
991	990
992	936
993	934
994	918
995	985
996	928
997	974
998	950
999	954
1000	3874319