1	828841947
2	74610672
3	25217630
4	13549627
5	9857507
6	9049573
7	9745523
8	11465470
9	14123770
10	17395275
11	20878886
12	24286969
13	27123626
14	29143723
15	30239683
16	30244121
17	29200980
18	27634495
19	25828888
20	23992594
21	22758320
22	22200820
23	22252091
24	22962546
25	24125464
26	25577243
27	27103886
28	28599164
29	29536977
30	30303335
31	30217864
32	29565703
33	28432151
34	26782171
35	24752866
36	22544827
37	20040367
38	17551783
39	15108411
40	12860990
41	10837239
42	9008949
43	7467112
44	6209033
45	5160944
46	4348941
47	3716490
48	3228320
49	2844938
50	2590451
51	2363460
52	2206820
53	2072002
54	1953172
55	1856345
56	1805831
57	1752628
58	1705435
59	1646162
60	1595501
61	1551503
62	1510249
63	1470042
64	1432897
65	1391038
66	1344078
67	1303342
68	1261788
69	1211123
70	1162651
71	1121165
72	1084187
73	1045219
74	996771
75	955976
76	923255
77	879170
78	849773
79	823112
80	786636
81	759485
82	731202
83	710509
84	688354
85	667853
86	649854
87	633163
88	620542
89	603235
90	587513
91	576322
92	564971
93	547938
94	538145
95	522873
96	514596
97	500181
98	489177
99	478735
100	467761
101	461761
102	449780
103	441381
104	429469
105	419646
106	410160
107	401091
108	391047
109	384249
110	374023
111	368604
112	364861
113	356708
114	350414
115	343316
116	337035
117	329717
118	324021
119	318418
120	313922
121	305516
122	300244
123	295590
124	291428
125	285129
126	281892
127	272790
128	267278
129	266528
130	259325
131	255558
132	252369
133	245750
134	241170
135	237510
136	232920
137	230280
138	227359
139	223478
140	216694
141	212625
142	211557
143	207870
144	205762
145	201069
146	198016
147	192514
148	190254
149	188546
150	187798
151	183910
152	182062
153	178149
154	175660
155	170392
156	167806
157	166198
158	164072
159	162478
160	159990
161	157749
162	155975
163	154801
164	152071
165	150743
166	148458
167	144189
168	143289
169	142292
170	138386
171	137901
172	136323
173	134481
174	131788
175	129742
176	127264
177	128092
178	125878
179	123533
180	122111
181	121245
182	120862
183	118374
184	117321
185	116002
186	114050
187	113739
188	111458
189	110079
190	110781
191	108512
192	106067
193	105467
194	104304
195	104626
196	103481
197	102775
198	100889
199	98845
200	97812
201	96698
202	95113
203	95133
204	93723
205	91710
206	92466
207	91005
208	90841
209	89181
210	87624
211	87117
212	86077
213	84898
214	84244
215	82790
216	82415
217	82664
218	80724
219	79894
220	80771
221	78617
222	78202
223	76977
224	76340
225	75327
226	74683
227	73166
228	73590
229	73174
230	73040
231	72662
232	70949
233	71360
234	70544
235	69662
236	69412
237	66924
238	67556
239	67117
240	66540
241	65973
242	66287
243	64185
244	64475
245	63788
246	62871
247	62397
248	62420
249	61374
250	61447
251	61146
252	60224
253	59672
254	59334
255	58405
256	57501
257	57013
258	56808
259	55185
260	55952
261	55595
262	54943
263	54417
264	54967
265	54018
266	53332
267	53477
268	52275
269	52887
270	51753
271	51625
272	51580
273	51193
274	50591
275	49991
276	49951
277	48808
278	48637
279	48412
280	48256
281	47688
282	47192
283	46589
284	47333
285	46403
286	45959
287	45586
288	45586
289	45097
290	44738
291	44140
292	43531
293	43545
294	43393
295	43226
296	42630
297	42734
298	42233
299	41786
300	41401
301	41378
302	40692
303	40474
304	39856
305	40506
306	40844
307	40005
308	39866
309	39370
310	39297
311	39252
312	38546
313	37933
314	37740
315	37201
316	37310
317	36727
318	36291
319	35947
320	35785
321	35679
322	35599
323	35356
324	35375
325	35331
326	35692
327	34904
328	35217
329	35064
330	34057
331	33884
332	33661
333	33764
334	33808
335	32948
336	32683
337	32670
338	32683
339	32637
340	32008
341	32262
342	31790
343	31372
344	31688
345	31133
346	31006
347	29666
348	30797
349	30287
350	30387
351	29920
352	29304
353	29737
354	29133
355	28506
356	28626
357	28672
358	28680
359	29052
360	28428
361	28322
362	28135
363	28353
364	27916
365	28028
366	27557
367	27217
368	26739
369	26446
370	26992
371	26546
372	26564
373	26442
374	26815
375	26352
376	26063
377	26470
378	26102
379	25784
380	25893
381	25595
382	25683
383	25657
384	25081
385	24839
386	24903
387	24519
388	24479
389	24314
390	24349
391	24707
392	24203
393	23833
394	24284
395	24507
396	23681
397	23739
398	23492
399	23666
400	23457
401	23059
402	23419
403	23631
404	23547
405	22534
406	22918
407	22349
408	22455
409	22488
410	22244
411	22121
412	21494
413	22287
414	21741
415	21798
416	21755
417	21331
418	21546
419	20996
420	21072
421	20923
422	21041
423	21486
424	21227
425	21141
426	20734
427	20142
428	20359
429	20332
430	20233
431	19801
432	19791
433	20054
434	19905
435	19872
436	19867
437	19772
438	19887
439	19524
440	19179
441	19089
442	19521
443	19265
444	19317
445	19101
446	18737
447	18909
448	19067
449	18716
450	18742
451	18114
452	18053
453	18139
454	18094
455	18095
456	17888
457	17926
458	17810
459	17990
460	17760
461	17454
462	17386
463	17351
464	17455
465	17202
466	17062
467	17045
468	17107
469	16861
470	17333
471	17141
472	16728
473	16551
474	16830
475	17337
476	16944
477	16352
478	16540
479	16251
480	16409
481	16030
482	16041
483	15969
484	16035
485	15964
486	15842
487	15853
488	15733
489	15213
490	15421
491	15471
492	15378
493	15570
494	15024
495	15028
496	14999
497	14912
498	14602
499	15030
500	14697
501	14821
502	14529
503	15018
504	14719
505	14346
506	14385
507	14143
508	14185
509	14258
510	13924
511	14406
512	14394
513	14374
514	13928
515	14040
516	14010
517	13913
518	14162
519	13778
520	13935
521	13709
522	13522
523	13738
524	13632
525	13557
526	13738
527	13495
528	13192
529	13097
530	13230
531	13154
532	13439
533	13260
534	13297
535	13164
536	13799
537	13549
538	13150
539	12948
540	13140
541	13386
542	13016
543	13067
544	13000
545	12918
546	13083
547	12829
548	12921
549	12765
550	12570
551	12680
552	12775
553	12593
554	12543
555	12207
556	12583
557	12547
558	12369
559	12364
560	12414
561	12618
562	12452
563	12558
564	12265
565	12715
566	12220
567	12028
568	12360
569	12454
570	12108
571	12000
572	12318
573	11976
574	11749
575	11348
576	11755
577	11802
578	11525
579	11472
580	11534
581	11354
582	11317
583	11287
584	11354
585	10970
586	11194
587	11616
588	11307
589	11332
590	11128
591	11278
592	11061
593	11129
594	11120
595	11079
596	10910
597	10875
598	10918
599	10862
600	10722
601	10809
602	10696
603	10606
604	10494
605	10610
606	10727
607	10635
608	10423
609	10793
610	10328
611	10733
612	10659
613	10858
614	10629
615	10666
616	10792
617	10538
618	10598
619	10701
620	10524
621	10526
622	10483
623	10335
624	10233
625	10470
626	10170
627	10218
628	10078
629	9828
630	9687
631	9971
632	9714
633	9447
634	9758
635	9676
636	9861
637	9572
638	9690
639	9649
640	9549
641	9756
642	9602
643	9518
644	9431
645	9299
646	9715
647	9388
648	9410
649	9242
650	9104
651	9159
652	9286
653	9059
654	9118
655	8790
656	8918
657	8792
658	8830
659	8924
660	8893
661	8563
662	8721
663	8472
664	8698
665	8935
666	8912
667	8330
668	8592
669	8767
670	8748
671	8805
672	8897
673	8896
674	8776
675	8479
676	8605
677	8590
678	8447
679	8558
680	8482
681	8454
682	8468
683	8228
684	8370
685	8297
686	8328
687	8433
688	8516
689	8372
690	8192
691	8346
692	8231
693	8355
694	8398
695	8324
696	8169
697	8116
698	8341
699	8058
700	8046
701	7984
702	8106
703	7882
704	7849
705	7927
706	7953
707	7991
708	7751
709	7983
710	7949
711	7950
712	7746
713	7830
714	7770
715	7854
716	7679
717	7671
718	7428
719	7704
720	7966
721	7486
722	7671
723	7615
724	7509
725	7484
726	7359
727	7468
728	7584
729	7569
730	7745
731	7534
732	7473
733	7452
734	7513
735	7561
736	7391
737	7386
738	7515
739	7431
740	7650
741	7276
742	7472
743	7298
744	7355
745	7090
746	7348
747	7257
748	7050
749	7169
750	7002
751	7164
752	6900
753	6842
754	6867
755	7051
756	6960
757	6961
758	6989
759	6994
760	6882
761	6970
762	6805
763	6727
764	6771
765	6729
766	6668
767	6824
768	6823
769	6676
770	6549
771	6738
772	6763
773	6823
774	6624
775	6442
776	6544
777	6485
778	6482
779	6572
780	6384
781	6589
782	6417
783	6293
784	6262
785	6419
786	6290
787	6499
788	6361
789	6453
790	6250
791	6401
792	6299
793	6240
794	6175
795	6438
796	6169
797	6288
798	6482
799	6376
800	6228
801	6280
802	6249
803	6159
804	6067
805	6255
806	6235
807	6117
808	5976
809	5986
810	6064
811	6001
812	6101
813	6121
814	5917
815	5831
816	5927
817	5900
818	6034
819	5971
820	5883
821	5965
822	5779
823	5899
824	5819
825	5863
826	5799
827	5764
828	5570
829	5763
830	5607
831	5844
832	5717
833	5640
834	5616
835	5856
836	5634
837	5577
838	5869
839	5553
840	5441
841	5382
842	5633
843	5420
844	5339
845	5368
846	5396
847	5475
848	5398
849	5311
850	5281
851	5242
852	5264
853	5336
854	5126
855	5181
856	5123
857	5172
858	5153
859	5164
860	5193
861	5259
862	5370
863	5407
864	5431
865	5540
866	5444
867	5298
868	5262
869	5184
870	5294
871	5134
872	5166
873	5331
874	5113
875	5140
876	5097
877	5214
878	5100
879	5157
880	5037
881	4835
882	5079
883	5145
884	5126
885	5187
886	5035
887	5173
888	5134
889	5164
890	5283
891	5233
892	5061
893	5066
894	5064
895	5010
896	4880
897	5030
898	5017
899	5032
900	4957
901	4980
902	5030
903	5155
904	4918
905	5115
906	4940
907	4904
908	4905
909	4988
910	4929
911	4922
912	4829
913	4899
914	4827
915	4802
916	4734
917	4813
918	4896
919	4841
920	4824
921	4831
922	4711
923	4994
924	4874
925	4795
926	4761
927	4663
928	4626
929	4732
930	4670
931	4548
932	4574
933	4578
934	4573
935	4619
936	4550
937	4518
938	4532
939	4485
940	4471
941	4550
942	4607
943	4738
944	4500
945	4715
946	4496
947	4599
948	4544
949	4527
950	4585
951	4607
952	4539
953	4402
954	4501
955	4612
956	4706
957	4531
958	4307
959	4307
960	4316
961	4394
962	4342
963	4332
964	4356
965	4556
966	4343
967	4222
968	4437
969	4360
970	4315
971	4281
972	4376
973	4275
974	4197
975	4170
976	4223
977	4256
978	4295
979	4356
980	4291
981	4472
982	4378
983	4493
984	4499
985	4348
986	4418
987	4395
988	4306
989	4388
990	4441
991	4235
992	4260
993	4257
994	4196
995	4162
996	4177
997	4371
998	4338
999	4251
1000	31799047