1	2
2	443
3	40819
4	74531
5	96763
6	518611
7	1102243
8	1835003
9	3321859
10	4148923
11	9834491
12	10370803
13	22692539
14	26574907
15	33191419
16	43606523
17	52706747
18	57696851
19	87410171
20	125893091
21	177885283
22	196661243
23	200568307
24	220881467
25	247012859
26	289952147
27	468463907
28	489541691
29	511242419
30	541161427
31	604456211
32	629407739
33	663731707
34	793659323
35	896168443
36	917675579
37	950577203
38	1030385659
39	1216187779
40	1337720827
41	1379961571
42	1467092083
43	1542442043
44	1604546491
45	1852265011
46	1887102947
47	2049284603
48	2240094523
49	2547960403
50	2591023619
51	2859629411
52	2929562939
53	3220697531
54	3399113587
55	3530508347
56	3803369467
57	3944919827
58	4031512571
59	4060655923
60	4119363299
61	4208481083
62	4483527491
63	5001618883
64	5415344419
65	5740180987
66	6270889403
67	6310000867
68	6428310331
69	6669347323
70	6874754483
71	7042084051
72	7126757507
73	7516192763
74	7560319027
75	7965252283
76	8671832563
77	9887274931
78	10535420947
79	11039692603
80	11153895419
81	13411051411
82	14136414203
83	14203623667
84	14542868027
85	14957039099
86	16692347387
87	16918255811
88	18316635059
89	18556937723
90	19373110843
91	19874115067
92	20555454971
93	20641701523
94	21606387707
95	22784665171
96	24196548091
97	24679820531
98	26472831779
99	27505467859
100	28457497147
101	29104233979
102	32719515131
103	32837070163
104	33907761211
105	34634331643
106	35247676403
107	35993196227
108	36369866171
109	38032480579
110	41922345467
111	44034506147
112	44177785339
113	46661306771
114	53192276867
115	53680774331
116	54666723323
117	55664671547
118	57184251203
119	60836941307
120	61014653779
121	64088938811
122	64272926083
123	66320078267
124	67075138363
125	67454808059
126	69374660539
127	70348098179
128	71133372067
129	72123154427
130	74739464851
131	76380529619
132	84947013139
133	87636431731
134	89002169923
135	93656987363
136	97495575907
137	102439487747
138	108589388483
139	108850839547
140	109637710051
141	116616692243
142	118268202467
143	119099772731
144	130562542651
145	134139402427
146	137475046739
147	145260730939
148	147812838203
149	151044784123
150	151696775099
151	160005611299
152	165825511931
153	167912801723
154	168262377187
155	173207495603
156	174637970131
157	178612338683
158	181908587891
159	182277321403
160	186741059899
161	190136269507
162	193188566531
163	199390810243
164	203730960827
165	205324676923
166	209750205107
167	211375118803
168	213828190627
169	215061811771
170	216300168499
171	218374644539
172	229806348851
173	230237235643
174	232833871867
175	238968455483
176	240740773051
177	242075746579
178	246110260027
179	248824687099
180	254313271291
181	262696561339
182	269342789627
183	277074653179
184	278051413691
185	286945759739
186	291968034619
187	294500999459
188	296537886787
189	300639794051
190	313701728251
191	316358702291
192	327681850043
193	330965942267
194	341510191843
195	358032080891
196	359771035619
197	368550314939
198	392042307827
199	392657436859
200	405095516219
201	410777293187
202	413319486883
203	424240843259
204	445987022483
205	446657343547
206	456792907027
207	471238617019
208	483153364451
209	494549146723
210	498146725883
211	514183408699
212	515658121211
213	520099171643
214	531313194323
215	538878053443
216	542687262203
217	543451251667
218	545747521531
219	547281956027
220	559661102779
221	570644795387
222	571434797299
223	573016987811
224	573809177083
225	575395745339
226	583372468219
227	593041430011
228	617679953851
229	645560158819
230	647276312531
231	653306798587
232	658505502139
233	660244512251
234	670742904827
235	674266940923
236	686698242491
237	689381819219
238	695670667771
239	711102562067
240	744531726899
241	748309470547
242	761632177763
243	768352423099
244	770279727611
245	790711359923
246	791693203387
247	799577227451
248	815501953723
249	820521442883
250	835703407163
251	844901854211
252	858307290619
253	861420856963
254	873950419939
255	876050420051
256	905804585779
257	907955288291
258	909031915003
259	914427816563
260	915509552827
261	924194170811
262	925283594083
263	930743554043
264	960598830179
265	965075400067
266	1043319225251
267	1044500341243
268	1058743332859
269	1087616581627
270	1091262220771
271	1093697167187
272	1094915997499
273	1123199605523
274	1138147723379
275	1153227881171
276	1160817656483
277	1172264644091
278	1187644014587
279	1195383886139
280	1199266400243
281	1226679641147
282	1231948122043
283	1234588009979
284	1238554908803
285	1243857312931
286	1246514180627
287	1258516909883
288	1267905452179
289	1271943364603
290	1294986898739
291	1315549118459
292	1325218849411
293	1327990306547
294	1333544807443
295	1346099017531
296	1378539424019
297	1388515032571
298	1399974521339
299	1417281703931
300	1427443125187
301	1440579022843
302	1449380907067
303	1461172422971
304	1465610675699
305	1478979339707
306	1480469745379
307	1492429052963
308	1530216672763
309	1533266937659
310	1547043297347
311	1585743409147
312	1593560073107
313	1618745940499
314	1631437781843
315	1642597415419
316	1650599662259
317	1657020139987
318	1661846409211
319	1681245199867
320	1691000950459
321	1704067223483
322	1710625525051
323	1720494494203
324	1738686051587
325	1780506427387
326	1788950168147
327	1794029203451
328	1821279817723
329	1840173799907
330	1850534466419
331	1855729351163
332	1866148268987
333	1881849652643
334	1894122546619
335	1909980234787
336	1920601045939
337	1924150046051
338	1934823273203
339	1968882080251
340	1983341377019
341	2005162786811
342	2051136929011
343	2056700588539
344	2084669844259
345	2111002206707
346	2128046699963
347	2139460513787
348	2185523888123
349	2232243736571
350	2285594041187
351	2311581597691
352	2315597083067
353	2317606568419
354	2321629026131
355	2366183656867
356	2378433073459
357	2396886351547
358	2438234838587
359	2475852660731
360	2490585664387
361	2522352958267
362	2528738658931
363	2533001774627
364	2554389236947
365	2571585628691
366	2584533448163
367	2638950547963
368	2652123321787
369	2738816326003
370	2750065557563
371	2793093533491
372	2797648727267
373	2799928180219
374	2804490799931
375	2887467690683
376	2889795667747
377	2943685076411
378	3029371955003
379	3058299450299
380	3080115507107
381	3102035066363
382	3156053471419
383	3193241466739
384	3288755965763
385	3291294892027
386	3326977181243
387	3337219279291
388	3375814341811
389	3388745179451
390	3474917772419
391	3525188651707
392	3533170207891
393	3578626687547
394	3594762755579
395	3646180169347
396	3700830980387
397	3703577762299
398	3717332060339
399	3725600962043
400	3728359985107
401	3742175534267
402	3769908936187
403	3792194054651
404	3800573562179
405	3834215031971
406	3904937842171
407	3990946631611
408	4040240889827
409	4092875457491
410	4122313432771
411	4166734533691
412	4220459679739
413	4235464855379
414	4247494570867
415	4289777924483
416	4307984927507
417	4399793058467
418	4524220190947
419	4558844175419
420	4580969333971
421	4590473416699
422	4599990635683
423	4634999639867
424	4654170110459
425	4686238234939
426	4724914009531
427	4750815719099
428	4773557219251
429	4793107600003
430	4829088467387
431	4848790073339
432	4858660939043
433	4871842919491
434	4878442841267
435	4898278365059
436	4928132349947
437	4981505163259
438	5079223024787
439	5092800802483
440	5236831197859
441	5278475784451
442	5285437941107
443	5330841235771
444	5457928851643
445	5605109199587
446	5608731631099
447	5619608289283
448	5714462276147
449	5729149257043
450	5751226879267
451	5780751836771
452	5806668917947
453	5840104549603
454	5847552078419
455	5873668286971
456	5881144316987
457	5903610463739
458	5948714254331
459	5986475764411
460	6112221983779
461	6119899046291
462	6158380797571
463	6247500288059
464	6286514540539
465	6341406874427
466	6353210937971
467	6357148878523
468	6380810698747
469	6460107361787
470	6484023818939
471	6520009069667
472	6572222447611
473	6616620116003
474	6653093848571
475	6677483985083
476	6693777147451
477	6767424405499
478	6800329166843
479	6837474318131
480	6866458324987
481	6903843678643
482	6928842484867
483	6991603359547
484	7025230252091
485	7029441179203
486	7050521056763
487	7088570958611
488	7156552796563
489	7177885908923
490	7194982890811
491	7259338350931
492	7293817636499
493	7371794836163
494	7481015635963
495	7502988450323
496	7533822610939
497	7622385455099
498	7689261142019
499	7774530386107
500	7837762121723
501	7842291747187
502	7883136934843
503	7905889865603
504	7978993375747
505	8006522943379
506	8015713517891
507	8071004698787
508	8084867108411
509	8089491436483
510	8131189764091
511	8140475476667
512	8159068104763
513	8285309343859
514	8356002729979
515	8379656243219
516	8493814618067
517	8512941234163
518	8536889854523
519	8541684961987
520	8565687434747
521	8584921755643
522	8594549704379
523	8710647128507
524	8715507076579
525	8788623367099
526	8832688806307
527	8876901293563
528	8886746284859
529	8950916211043
530	8980636993267
531	9010423493059
532	9050241178883
533	9080181301907
534	9205642619707
535	9281471256787
536	9311918923939
537	9383222279027
538	9398548773371
539	9460021645307
540	9583770370043
541	9635649202363
542	9771409618427
543	9776656482259
544	9855584976379
545	9871421478403
546	9881988565619
547	9919032754171
548	10025383169531
549	10030720551763
550	10202518665299
551	10354441656883
552	10414535875067
553	10518881832643
554	10712918200763
555	10763196024611
556	10852966790563
557	11073871198651
558	11085279718907
559	11090986916179
560	11136715030163
561	11159626145971
562	11274653173331
563	11280425179963
564	11332461913411
565	11489531804347
566	11518777162307
567	11536348175291
568	11553937048019
569	11571543789563
570	11606810915387
571	11665748570107
572	11730810057059
573	11784221757947
574	11873601115427
575	11897511699523
576	11927445042683
577	12059748275899
578	12077865070483
579	12162650042531
580	12290570027003
581	12345666307571
582	12425540145979
583	12530509371011
584	12592531248691
585	12642295846259
586	12779824155331
587	12874163029051
588	12893086342579
589	12981640347587
590	13000668807611
591	13083340350019
592	13159962939811
593	13211210506979
594	13236884107267
595	13288331048771
596	13333456325947
597	13625988930787
598	13843210784251
599	14015972074043
600	14122997808187
601	14196893160179
602	14277799749971
603	14298074312699
604	14325136906747
605	14420124875963
606	15145953175523
607	15301054057459
608	15364808367547
609	15386099092051
610	15578601357307
611	15657486253859
612	15765485089979
613	15794368414267
614	15859484830723
615	15873979408499
616	15895737829883
617	16012118610427
618	16070521417211
619	16165728573619
620	16231861017787
621	16342482135667
622	16401685032371
623	16475889497251
624	16602550139387
625	16624969183811
626	16737367183931
627	16782467849723
628	16812579926011
629	17123308022963
630	17291607394819
631	17330010417659
632	17399279067347
633	17422409568251
634	17515136568827
635	17522878635859
636	17584897320083
637	17709373348627
638	17732777803771
639	17779648557883
640	17818770551843
641	17983709642747
642	18173454143483
643	18324611534371
644	18348554839099
645	18364528623611
646	18444536623291
647	18460566057467
648	18532813443923
649	18564983805811
650	18581082938147
651	18710211185059
652	18807448987651
653	19027464587707
654	19052016151891
655	19068395588867
656	19142219235323
657	19150433604787
658	19216233176051
659	19240946819579
660	19265681643203
661	19340013285371
662	19647607721107
663	19697793157219
664	19865695026179
665	20221389023411
666	20486630965243
667	20503822542779
668	20633066037299
669	21155471119379
670	21243386803459
671	21349206718051
672	21668773778563
673	21722343034387
674	21937502944723
675	22072696708603
676	22117884418163
677	22126929354427
678	22172191025987
679	22308346295867
680	22527352230203
681	22563991993531
682	22582326764027
683	22729362614779
684	22775441860019
685	22914053177339
686	23277072103427
687	23474122330619
688	23502362816963
689	23681745372091
690	23738581536763
691	24129397677107
692	24311952741883
693	24427723751419
694	24689551047331
695	24718757926459
696	24855361280507
697	25090707701243
698	25179344163731
699	25278073671811
700	25446505541627
701	25476306260771
702	25625658901691
703	25685563015163
704	25775594116211
705	25785610538683
706	25805651167739
707	25895962502867
708	26057035801939
709	26087311208443
710	26107507835579
711	26198521661027
712	26360845847779
713	26381183390291
714	26534048482811
715	26544260432083
716	26564692190339
717	26636285906491
718	26810691642947
719	26944573211131
720	27841494321083
721	27904802394107
722	28042298962771
723	28095302286011
724	28715029507579
725	28768876904819
726	29136825508387
727	29300148142267
728	29365647704059
729	29617633612163
730	29661603863971
731	29793775688707
732	29948471706323
733	30014933584547
734	30125921763667
735	30326389349251
736	30415770766019
737	30527744285299
738	30561389849083
739	30786325577723
740	30865313057539
741	31091735777699
742	31582288680763
743	31743109920251
744	31950681066299
745	32124346667219
746	32228847472187
747	32298640428539
748	32450204010163
749	32508623710523
750	32555409921211
751	32943110140579
752	33002119757819
753	33037559329763
754	33049378156027
755	33298225068019
756	33440982537811
757	33620002407931
758	33751688914883
759	33871701919603
760	34004044436987
761	34052254322683
762	34076376343739
763	34185066416867
764	34293987363323
765	34366729711547
766	34524690862531
767	34854309104827
768	34964646266083
769	34989197216339
770	35284705596947
771	35297054420539
772	35334118177843
773	35581873161683
774	35594291218747
775	35693739704891
776	35780908934227
777	35918175698939
778	36005709801091
779	36193761527611
780	36256590633251
781	36269165173243
782	36521266905083
783	36597124578107
784	36863453541539
785	36952516149691
786	36977988931067
787	37016220048131
788	37028969607163
789	37683086053027
790	37760543554099
791	37876928709307
792	38266606006267
793	38606480511419
794	38764022065211
795	38803474306739
796	38842953307643
797	38895633616891
798	39001137086459
799	39318791852027
800	39451655420347
801	39638166765563
802	40039811441723
803	40322571091427
804	40336068939259
805	40457685145747
806	40701650431171
807	40783189606483
808	40810393511939
809	40851222048443
810	40932960796667
811	40946594512819
812	41014808505659
813	41069434214587
814	41178831096251
815	41357015073859
816	41549479545107
817	41563249809979
818	41604578858803
819	41687319130627
820	41770169028499
821	41797810035011
822	42019377204163
823	42436923458323
824	42590714048507
825	43054314255731
826	43308599170979
827	43649200471907
828	43691900773691
829	44048820109891
830	44206478427323
831	44335751054051
832	44350130216443
833	44566190881123
834	45087597023107
835	45131230178491
836	45218580922363
837	45437450731843
838	45598403338427
839	45833194056379
840	46054041062899
841	46186889176507
842	46260803953667
843	46319992521763
844	46394049200123
845	46497861099139
846	47168923221499
847	47604788381747
848	47967528362483
849	48210375847027
850	48484557424291
851	48530355177019
852	48560903028731
853	48943833426931
854	49066794952499
855	49205372638907
856	49483310281211
857	49498781873683
858	49576188211643
859	49762292582459
860	49871068243411
861	49948862117051
862	50857191028219
863	50983335305723
864	51141308758843
865	51172942557179
866	51220417709603
867	51696785198963
868	51840269204411
869	52000006980091
870	52096006968763
871	52176097157123
872	52192125038587
873	52336523704243
874	52803619602491
875	53159816166907
876	53452438353211
877	53550217179643
878	53991697672579
879	54073718669819
880	54468575913467
881	54633665443387
882	54683257269811
883	54865350711803
884	54964844573627
885	55214105305907
886	55264047709691
887	55364022847163
888	55464118484987
889	55564334695739
890	55631212523707
891	55815403205459
892	56185003354531
893	56437936664251
894	56471718349307
895	57048071266363
896	57235374504947
897	57491448082427
898	57508546758259
899	58178042560507
900	58316014145531
901	58592611381243
902	58679227034003
903	58783278441827
904	59322837357499
905	59480099583907
906	59900823756643
907	60164781179323
908	60358841999507
909	60464869022819
910	60624142254587
911	60730479646139
912	60961303754563
913	61050237756923
914	61157072681147
915	61210536850451
916	61228365162043
917	61478325131771
918	61585658749883
919	61872492330427
920	62034226907683
921	62286373849331
922	62340494078459
923	62412703137787
924	62503042846547
925	63101472191291
926	63648802663931
927	63667101313363
928	63868617981947
929	63978715173179
930	64715931491899
931	65086653897659
932	65142384071123
933	65365622889779
934	65533386288827
935	65832340641979
936	65869773738491
937	66395327975419
938	66848021839867
939	66904752831331
940	67568987703611
941	67816818786019
942	67855000347731
943	67912299556859
944	67969631013923
945	68256772335803
946	68371854917627
947	69007121980211
948	69490995892411
949	69549212305939
950	69607461224443
951	69899193709123
952	69938152850099
953	70191740179003
954	70661510450491
955	71310860304259
956	72242541641531
957	72781414635827
958	73081943130107
959	73343069386771
960	73463798694883
961	73948040802211
962	74008720263739
963	74069432910643
964	74556329848051
965	74719101728819
966	74780202208763
967	74800576435027
968	75475003818811
969	75536515636339
970	75782897118931
971	75824012714627
972	76009216933883
973	76711598824891
974	76939762962323
975	77022843775411
976	77376604484027
977	77710543694779
978	77752353527291
979	77815096390019
980	77961627648571
981	78213251858107
982	79649355236411
983	79713114389939
984	79989797256763
985	80224412991347
986	80288478624251
987	80352578355779
988	80609318449571
989	80823685818451
990	80952488480803
991	80995453091219
992	81533794031419
993	81598554786163
994	82161251712227
995	82248049400323
996	83535424939451
997	83689049905267
998	84084950143651
999	84460000532987
1000	84482096983699