1	2004118151
2	138099937
3	55085949
4	53664237
5	63234263
6	73825256
7	83147194
8	90460041
9	95760221
10	98430580
11	99710310
12	98845174
13	96667907
14	93766703
15	90334094
16	86701917
17	82623789
18	79230957
19	75679583
20	72067522
21	68751226
22	65238531
23	61748937
24	58477482
25	55341688
26	52021492
27	48630538
28	45325030
29	41905070
30	38565171
31	35419281
32	32236234
33	29091479
34	26057717
35	23154129
36	20413977
37	17875659
38	15595559
39	13528198
40	11664847
41	9965093
42	8499866
43	7180630
44	6085062
45	5140809
46	4340141
47	3674661
48	3122032
49	2643775
50	2275724
51	1960109
52	1690714
53	1474689
54	1305130
55	1166074
56	1053558
57	956081
58	881664
59	821437
60	763091
61	719065
62	675304
63	637510
64	607747
65	578588
66	554924
67	533901
68	510273
69	488057
70	469205
71	451950
72	432584
73	417246
74	395853
75	379756
76	367461
77	356484
78	346459
79	334377
80	324790
81	315818
82	307396
83	297660
84	287706
85	277016
86	272120
87	264829
88	260221
89	253945
90	248648
91	244515
92	237375
93	232156
94	225860
95	221562
96	216221
97	211274
98	205572
99	199688
100	195579
101	190748
102	184837
103	182717
104	176256
105	171909
106	169424
107	163613
108	159423
109	156537
110	153522
111	150786
112	149615
113	143139
114	141944
115	140972
116	137526
117	134259
118	131148
119	128821
120	125765
121	121338
122	118771
123	115053
124	114169
125	112683
126	110378
127	108965
128	106653
129	105554
130	103569
131	103239
132	101172
133	98935
134	96163
135	94636
136	94173
137	92818
138	91731
139	88704
140	87191
141	85956
142	84387
143	83059
144	82023
145	80531
146	80128
147	78438
148	76553
149	75286
150	73645
151	72318
152	71057
153	70035
154	69191
155	67842
156	66155
157	65503
158	65301
159	64602
160	64552
161	63684
162	62602
163	62540
164	61254
165	60564
166	59942
167	58803
168	58832
169	58060
170	57355
171	57216
172	56409
173	54626
174	54228
175	54438
176	53657
177	52533
178	50904
179	49866
180	49099
181	48347
182	48271
183	46993
184	46849
185	46101
186	45696
187	45520
188	45170
189	44763
190	44474
191	44167
192	43264
193	42867
194	42377
195	41323
196	41099
197	40893
198	40734
199	40448
200	39937
201	39632
202	39691
203	39103
204	38672
205	38148
206	37621
207	36824
208	36816
209	36572
210	36452
211	36068
212	35632
213	35621
214	34945
215	34419
216	33983
217	33557
218	33446
219	33195
220	33022
221	32339
222	32138
223	32051
224	32101
225	31290
226	30689
227	30528
228	30833
229	30307
230	30338
231	29702
232	29508
233	28617
234	28777
235	29054
236	28253
237	28207
238	27518
239	27703
240	27364
241	27140
242	26392
243	26502
244	26701
245	26435
246	26593
247	26606
248	26058
249	25929
250	25646
251	25767
252	25552
253	24929
254	24754
255	24602
256	24414
257	24168
258	23873
259	23946
260	23815
261	23474
262	23587
263	23366
264	23121
265	22614
266	22292
267	22430
268	22686
269	22674
270	22190
271	21875
272	21713
273	21478
274	21627
275	21259
276	21151
277	20451
278	20828
279	20794
280	20780
281	20686
282	20345
283	19973
284	19817
285	19756
286	19595
287	19143
288	19314
289	19562
290	19215
291	19077
292	18872
293	19215
294	19103
295	18942
296	18731
297	18390
298	18461
299	18223
300	18144
301	17784
302	17872
303	17782
304	17824
305	17902
306	17455
307	17650
308	17526
309	17437
310	16559
311	16686
312	16810
313	17009
314	16495
315	16554
316	16131
317	16336
318	16096
319	16159
320	16356
321	16200
322	15954
323	16060
324	15933
325	16085
326	15540
327	15565
328	15568
329	15413
330	15266
331	15179
332	15211
333	14966
334	14930
335	14558
336	14556
337	14467
338	14496
339	14642
340	14495
341	14374
342	14191
343	13978
344	13997
345	14205
346	14138
347	14044
348	13978
349	13644
350	13820
351	13765
352	13579
353	13369
354	13188
355	13187
356	12929
357	13041
358	13189
359	12838
360	12849
361	12826
362	12783
363	12918
364	12610
365	12626
366	12564
367	12428
368	12271
369	12204
370	12325
371	12160
372	11974
373	11983
374	11925
375	11794
376	11941
377	11948
378	11803
379	11728
380	11535
381	11602
382	11712
383	11535
384	11539
385	11418
386	11551
387	11333
388	11547
389	11304
390	11375
391	11378
392	11052
393	11055
394	10986
395	10910
396	10811
397	10987
398	10864
399	10847
400	10856
401	10819
402	10495
403	10569
404	10579
405	10654
406	10635
407	10360
408	10577
409	10695
410	10390
411	10241
412	10353
413	10084
414	10251
415	10299
416	9859
417	9806
418	10012
419	9874
420	9835
421	9620
422	9448
423	9586
424	9627
425	9619
426	9492
427	9459
428	9526
429	9380
430	9099
431	9145
432	8998
433	9273
434	9282
435	9150
436	8928
437	8851
438	8874
439	8778
440	8945
441	8813
442	9047
443	8552
444	8715
445	8693
446	8576
447	8529
448	8282
449	8546
450	8209
451	8559
452	8527
453	8221
454	8460
455	8521
456	8228
457	8252
458	8346
459	8250
460	8247
461	8183
462	7868
463	8150
464	7911
465	8116
466	8019
467	7817
468	7747
469	7704
470	7751
471	7615
472	7638
473	7751
474	7564
475	7364
476	7253
477	7501
478	7549
479	7536
480	7556
481	7581
482	7591
483	7449
484	7328
485	7303
486	7272
487	7336
488	7139
489	7191
490	7192
491	7237
492	7102
493	7070
494	7029
495	6855
496	7166
497	6994
498	6883
499	6978
500	6855
501	6841
502	6706
503	6910
504	6773
505	6753
506	6786
507	6917
508	6772
509	6758
510	6624
511	6557
512	6641
513	6656
514	6568
515	6531
516	6668
517	6611
518	6510
519	6573
520	6429
521	6647
522	6417
523	6443
524	6435
525	6579
526	6463
527	6261
528	6242
529	6307
530	6430
531	6255
532	6285
533	6133
534	6326
535	6233
536	6236
537	6057
538	5967
539	6164
540	6094
541	6204
542	6052
543	6164
544	5899
545	6139
546	6048
547	6051
548	5842
549	5856
550	5856
551	5904
552	5950
553	5896
554	5890
555	5822
556	5713
557	5712
558	5817
559	5487
560	5497
561	5415
562	5545
563	5583
564	5314
565	5453
566	5368
567	5416
568	5354
569	5380
570	5336
571	5505
572	5325
573	5326
574	5435
575	5383
576	5147
577	5305
578	5073
579	5188
580	5191
581	5265
582	5159
583	5177
584	5271
585	5274
586	5157
587	5175
588	5043
589	5087
590	5222
591	5294
592	5112
593	5271
594	5012
595	4891
596	5070
597	5009
598	4848
599	4851
600	4946
601	4888
602	4949
603	4729
604	4975
605	4877
606	4942
607	4920
608	4906
609	4885
610	4937
611	4853
612	4900
613	4695
614	4911
615	4812
616	4722
617	4812
618	4740
619	4734
620	4571
621	4736
622	4597
623	4710
624	4756
625	4660
626	4670
627	4616
628	4621
629	4553
630	4543
631	4468
632	4560
633	4633
634	4502
635	4437
636	4609
637	4533
638	4385
639	4272
640	4302
641	4484
642	4513
643	4576
644	4373
645	4302
646	4452
647	4276
648	4373
649	4389
650	4411
651	4188
652	4299
653	4293
654	4271
655	4341
656	4382
657	4349
658	4388
659	4149
660	4220
661	4197
662	4194
663	4134
664	4079
665	4287
666	4092
667	4135
668	4159
669	4095
670	4089
671	4109
672	3964
673	3916
674	3911
675	4065
676	3911
677	3960
678	3992
679	3984
680	3906
681	3980
682	3878
683	3901
684	3909
685	3811
686	3904
687	3915
688	3873
689	4082
690	3953
691	3910
692	3746
693	3757
694	3933
695	3762
696	3681
697	3733
698	3641
699	3730
700	3767
701	3745
702	3598
703	3670
704	3706
705	3743
706	3705
707	3599
708	3598
709	3632
710	3648
711	3655
712	3763
713	3538
714	3573
715	3483
716	3424
717	3505
718	3482
719	3424
720	3355
721	3435
722	3530
723	3500
724	3484
725	3467
726	3574
727	3527
728	3515
729	3464
730	3379
731	3349
732	3290
733	3232
734	3287
735	3326
736	3437
737	3295
738	3278
739	3192
740	3318
741	3182
742	3262
743	3373
744	3184
745	3293
746	3244
747	3184
748	3258
749	3260
750	3182
751	3196
752	3260
753	3200
754	3219
755	3199
756	3245
757	3068
758	3149
759	3144
760	3077
761	3063
762	2969
763	2957
764	3032
765	3069
766	3045
767	2992
768	3042
769	2926
770	2996
771	2971
772	3039
773	2996
774	3073
775	2935
776	2986
777	3054
778	2870
779	2912
780	2980
781	2942
782	2851
783	2890
784	2875
785	2959
786	2912
787	2896
788	2889
789	2802
790	2689
791	2757
792	2845
793	2802
794	2771
795	2824
796	2747
797	2741
798	2775
799	2781
800	2720
801	2705
802	2727
803	2710
804	2700
805	2619
806	2684
807	2746
808	2723
809	2642
810	2731
811	2669
812	2663
813	2567
814	2666
815	2584
816	2694
817	2619
818	2648
819	2519
820	2460
821	2612
822	2637
823	2494
824	2601
825	2525
826	2469
827	2410
828	2513
829	2500
830	2513
831	2521
832	2468
833	2480
834	2477
835	2567
836	2426
837	2535
838	2392
839	2439
840	2337
841	2336
842	2483
843	2435
844	2440
845	2375
846	2335
847	2423
848	2335
849	2355
850	2271
851	2309
852	2394
853	2327
854	2289
855	2268
856	2127
857	2278
858	2349
859	2310
860	2314
861	2196
862	2188
863	2317
864	2190
865	2234
866	2250
867	2200
868	2241
869	2274
870	2204
871	2216
872	2244
873	2208
874	2108
875	2124
876	2162
877	2106
878	2238
879	2123
880	2073
881	2169
882	2046
883	2088
884	2107
885	2096
886	2134
887	2079
888	2104
889	2081
890	2077
891	2084
892	2129
893	2077
894	2142
895	2067
896	2100
897	1973
898	2032
899	2079
900	2038
901	2065
902	2011
903	2017
904	2104
905	2079
906	2015
907	2073
908	2052
909	1930
910	1956
911	1935
912	1943
913	1941
914	2003
915	1977
916	1941
917	1817
918	1899
919	1889
920	1935
921	1943
922	1865
923	1926
924	1968
925	1898
926	1931
927	1936
928	1900
929	1885
930	1809
931	1881
932	1930
933	1890
934	1782
935	1873
936	2046
937	1891
938	1785
939	1853
940	1861
941	1866
942	1784
943	1725
944	1777
945	1794
946	1788
947	1888
948	1764
949	1842
950	1860
951	1728
952	1769
953	1849
954	1758
955	1781
956	1845
957	1830
958	1756
959	1828
960	1709
961	1777
962	1850
963	1793
964	1796
965	1810
966	1745
967	1779
968	1688
969	1732
970	1734
971	1676
972	1771
973	1804
974	1692
975	1730
976	1721
977	1639
978	1656
979	1656
980	1665
981	1613
982	1685
983	1678
984	1756
985	1717
986	1682
987	1701
988	1653
989	1679
990	1622
991	1625
992	1572
993	1560
994	1640
995	1587
996	1653
997	1614
998	1650
999	1561
1000	7792639