1	2
2	8
3	238
4	310
5	338
6	442
7	542
8	688
9	698
10	872
11	920
12	1198
13	1330
14	1382
15	1538
16	1558
17	1678
18	1702
19	1712
20	1768
21	1882
22	2032
23	2080
24	2102
25	2260
26	2312
27	2408
28	2440
29	2540
30	2642
31	3112
32	3170
33	3188
34	3268
35	3320
36	3580
37	3740
38	3742
39	3770
40	3980
41	4028
42	4048
43	4148
44	4292
45	4472
46	4522
47	4628
48	4820
49	4870
50	5030
51	5132
52	5158
53	5288
54	5300
55	5840
56	5912
57	5920
58	5942
59	6040
60	6118
61	6322
62	6592
63	6608
64	6722
65	6860
66	6880
67	7012
68	7270
69	7288
70	7360
71	7592
72	7672
73	7792
74	8008
75	8110
76	8150
77	8152
78	8252
79	8272
80	8372
81	8510
82	8540
83	8620
84	8770
85	8828
86	8852
87	8858
88	8948
89	9152
90	9412
91	9442
92	9550
93	9560
94	9668
95	9712
96	9820
97	9832
98	9838
99	10012
100	10202
101	10360
102	10678
103	10700
104	10958
105	11510
106	11528
107	11612
108	11872
109	12352
110	12400
111	12410
112	12640
113	12800
114	12802
115	12998
116	13022
117	13090
118	13160
119	13210
120	13322
121	13412
122	13418
123	13628
124	13810
125	13840
126	13862
127	13870
128	14168
129	14312
130	14342
131	14660
132	14662
133	14720
134	14728
135	14960
136	14972
137	15080
138	15088
139	15142
140	15290
141	15622
142	15712
143	15748
144	15938
145	15988
146	15998
147	16072
148	16138
149	16162
150	16172
151	16330
152	16502
153	16552
154	16700
155	16820
156	16928
157	16978
158	17068
159	17350
160	17380
161	17630
162	17672
163	17758
164	17878
165	17968
166	17992
167	18032
168	18082
169	18320
170	18400
171	18728
172	19070
173	19118
174	19148
175	19252
176	19268
177	19720
178	20138
179	20252
180	20348
181	20578
182	20632
183	20810
184	20918
185	21148
186	21152
187	21188
188	21200
189	21328
190	21442
191	21452
192	21562
193	21608
194	21640
195	21650
196	21722
197	21748
198	22040
199	22088
200	22108
201	22160
202	22240
203	22322
204	22438
205	22502
206	22580
207	22598
208	22660
209	22682
210	22910
211	23012
212	23062
213	23162
214	23402
215	23522
216	23740
217	23800
218	23870
219	24038
220	24068
221	24202
222	24260
223	24428
224	24632
225	24722
226	24892
227	25042
228	25082
229	25108
230	25130
231	25228
232	25238
233	25258
234	25580
235	25750
236	25768
237	25802
238	26212
239	26572
240	26678
241	26680
242	26732
243	26752
244	26818
245	27088
246	27122
247	27260
248	27430
249	27500
250	27562
251	27752
252	27868
253	27910
254	28000
255	28040
256	28220
257	28310
258	28508
259	28520
260	28688
261	28810
262	28928
263	29032
264	29162
265	29212
266	29482
267	29518
268	29552
269	29590
270	29642
271	29758
272	29858
273	29992
274	30058
275	30238
276	30248
277	30302
278	30340
279	30418
280	30458
281	30598
282	30640
283	30718
284	30748
285	30788
286	30812
287	30902
288	31118
289	31478
290	31598
291	31898
292	32018
293	32032
294	32308
295	32440
296	32570
297	32680
298	33110
299	33158
300	33418
301	33518
302	33550
303	33592
304	33668
305	33692
306	33802
307	33982
308	34142
309	34198
310	35012
311	35378
312	35420
313	35572
314	36098
315	36592
316	36688
317	36772
318	36850
319	36892
320	37010
321	37388
322	37478
323	37748
324	37762
325	37882
326	37918
327	38008
328	38120
329	38260
330	38342
331	38770
332	38872
333	39070
334	39082
335	39238
336	39320
337	39442
338	39520
339	39848
340	39962
341	40078
342	40090
343	40220
344	40388
345	41002
346	41128
347	41218
348	41300
349	41402
350	41638
351	41728
352	41792
353	41872
354	42020
355	42320
356	42460
357	42560
358	42682
359	42952
360	43120
361	43562
362	43690
363	43760
364	43792
365	43798
366	44150
367	44242
368	44342
369	44498
370	44872
371	45020
372	45088
373	45202
374	45328
375	45502
376	45992
377	46010
378	46088
379	46150
380	46228
381	46238
382	46282
383	46330
384	46432
385	46610
386	46678
387	46708
388	46778
389	46978
390	47330
391	47572
392	47590
393	47608
394	47740
395	47930
396	48182
397	48352
398	48382
399	48428
400	48452
401	48500
402	48508
403	48680
404	48752
405	48758
406	48958
407	49000
408	49028
409	49090
410	49180
411	49210
412	49228
413	49282
414	49292
415	49298
416	49310
417	49448
418	49520
419	49612
420	49802
421	49828
422	49852
423	49910
424	49948
425	50090
426	50338
427	50410
428	50438
429	50528
430	50540
431	50840
432	50852
433	50938
434	51230
435	51260
436	51622
437	51758
438	51782
439	51790
440	52028
441	52132
442	52168
443	52262
444	52382
445	52522
446	52672
447	52792
448	52858
449	52870
450	52960
451	53180
452	53188
453	53348
454	53590
455	53600
456	54130
457	54160
458	54218
459	54302
460	54368
461	54520
462	54608
463	54742
464	54812
465	54980
466	55030
467	55058
468	55138
469	55142
470	55312
471	55340
472	55420
473	55432
474	55442
475	55510
476	55832
477	56198
478	56330
479	56450
480	56542
481	56548
482	56888
483	56900
484	56942
485	57028
486	57322
487	57568
488	57938
489	58022
490	58192
491	58238
492	58322
493	58462
494	58510
495	58612
496	58648
497	58750
498	58928
499	58960
500	58990
501	59168
502	59372
503	59408
504	59498
505	59500
506	59512
507	59618
508	59692
509	59732
510	59740
511	59782
512	59978
513	60332
514	60452
515	60610
516	60862
517	60958
518	61052
519	61130
520	61160
521	61202
522	61270
523	61472
524	61598
525	61762
526	61780
527	61870
528	61880
529	61930
530	62102
531	62248
532	62272
533	62312
534	62320
535	62390
536	62422
537	62528
538	62762
539	62828
540	63038
541	63320
542	63788
543	63860
544	63920
545	63952
546	63962
547	63988
548	64160
549	64700
550	64718
551	64832
552	65030
553	65230
554	65252
555	65302
556	65408
557	65590
558	65662
559	65828
560	66010
561	66088
562	66100
563	66122
564	66298
565	66308
566	66350
567	66548
568	66638
569	66752
570	66818
571	66922
572	66952
573	67168
574	67220
575	67330
576	67700
577	67862
578	67948
579	68050
580	68278
581	68302
582	68408
583	68480
584	68872
585	69248
586	69308
587	69338
588	69418
589	69422
590	69458
591	69860
592	69928
593	70228
594	70390
595	70810
596	70888
597	71008
598	71110
599	71188
600	71438
601	71582
602	71830
603	71860
604	72050
605	72062
606	72172
607	72232
608	72272
609	72280
610	72328
611	73142
612	73238
613	73348
614	73480
615	73702
616	74050
617	74240
618	74362
619	74428
620	74590
621	74620
622	74698
623	74968
624	75038
625	75100
626	75128
627	75140
628	75410
629	75448
630	75532
631	75728
632	75730
633	76088
634	76258
635	76312
636	76510
637	76552
638	76678
639	77182
640	77260
641	77360
642	77362
643	77378
644	78148
645	78308
646	78478
647	78512
648	78598
649	78688
650	78692
651	78868
652	78932
653	79058
654	79178
655	79208
656	79250
657	79298
658	79412
659	79990
660	80002
661	80212
662	80392
663	80462
664	81128
665	81470
666	81632
667	81758
668	81808
669	81902
670	82132
671	82282
672	82292
673	82390
674	82502
675	82520
676	82540
677	82772
678	82792
679	82820
680	82840
681	82942
682	83002
683	83030
684	83078
685	83248
686	83282
687	83332
688	83632
689	83642
690	83738
691	83998
692	84152
693	84592
694	84622
695	84632
696	84778
697	85100
698	85202
699	85262
700	85432
701	85480
702	85618
703	85790
704	85808
705	85892
706	86180
707	86302
708	86530
709	86662
710	86758
711	86800
712	86920
713	86948
714	87038
715	87232
716	87268
717	87790
718	87820
719	88190
720	88220
721	88280
722	88322
723	88630
724	88642
725	88690
726	88712
727	88802
728	88868
729	89048
730	89098
731	89282
732	89392
733	89458
734	89500
735	89618
736	90028
737	90130
738	90172
739	90548
740	90610
741	90622
742	90922
743	91250
744	91312
745	91450
746	91532
747	91828
748	91868
749	91912
750	92048
751	92350
752	92378
753	92498
754	92558
755	92560
756	92678
757	92758
758	92960
759	93170
760	93200
761	93500
762	93728
763	94018
764	94070
765	94118
766	94210
767	94280
768	94352
769	94418
770	94420
771	94430
772	94762
773	94832
774	94892
775	94918
776	95300
777	95320
778	95432
779	95600
780	95692
781	95732
782	95740
783	95812
784	95978
785	96058
786	96088
787	96112
788	96238
789	96280
790	96320
791	96628
792	96640
793	96650
794	96680
795	96728
796	96760
797	96860
798	96932
799	97388
800	97658
801	97990
802	98018
803	98068
804	98150
805	98162
806	98320
807	98362
808	98368
809	98510
810	98600
811	99172
812	99178
813	99338
814	99380
815	99428
816	99892
817	100058
818	100070
819	100268
820	100322
821	100408
822	100532
823	100622
824	100630
825	100738
826	101332
827	101348
828	101438
829	101638
830	101828
831	101942
832	101968
833	102182
834	102208
835	102262
836	102508
837	102580
838	102610
839	102620
840	102730
841	102820
842	102962
843	103112
844	103268
845	103328
846	103372
847	103420
848	103660
849	104012
850	104078
851	104102
852	104140
853	104272
854	104300
855	104338
856	104420
857	104548
858	104590
859	104620
860	104680
861	104908
862	105388
863	105518
864	105682
865	105740
866	106018
867	106192
868	106612
869	106630
870	106642
871	106810
872	107060
873	107072
874	107300
875	107302
876	107572
877	107648
878	107990
879	108022
880	108212
881	108230
882	108238
883	108442
884	108568
885	108670
886	109040
887	109078
888	109162
889	109252
890	109370
891	109378
892	109450
893	109498
894	109672
895	109862
896	110218
897	110288
898	110420
899	110620
900	110822
901	110998
902	111328
903	111718
904	111920
905	111928
906	111992
907	112048
908	112058
909	112172
910	112552
911	112702
912	112828
913	113000
914	113122
915	113258
916	113452
917	113572
918	113732
919	113998
920	114100
921	114140
922	114320
923	114422
924	114590
925	114728
926	114802
927	115132
928	115228
929	115438
930	115492
931	115630
932	115742
933	115828
934	115912
935	116042
936	116072
937	116510
938	116602
939	116690
940	116758
941	116852
942	116948
943	117350
944	117460
945	117548
946	117560
947	117980
948	118160
949	118252
950	118292
951	118328
952	118478
953	118522
954	118652
955	118820
956	118862
957	118940
958	118948
959	119002
960	119188
961	119192
962	119228
963	119522
964	119722
965	119770
966	119782
967	119842
968	120148
969	120158
970	120292
971	120502
972	120830
973	121402
974	121442
975	121588
976	121658
977	121880
978	121930
979	121952
980	122270
981	122602
982	123370
983	123422
984	123490
985	123700
986	123932
987	124180
988	124940
989	124972
990	125050
991	125062
992	125090
993	125330
994	125368
995	125578
996	125890
997	125918
998	125962
999	126100
1000	126200
1001	126440
1002	126682
1003	126700
1004	126872
1005	126980
1006	127090
1007	127262
1008	127438
1009	127840
1010	127868
1011	127958
1012	128042
1013	128230
1014	128332
1015	128360
1016	128452
1017	129280
1018	129592
1019	129608
1020	129670
1021	129842
1022	129848
1023	129932
1024	130042
1025	130130
1026	130180
1027	130378
1028	130382
1029	130492
1030	130700
1031	130862
1032	130900
1033	130970
1034	131032
1035	131312
1036	131672
1037	132062
1038	132122
1039	132142
1040	132188
1041	132430
1042	132532
1043	132562
1044	132592
1045	132638
1046	132770
1047	132812
1048	132832
1049	132952
1050	133082
1051	133262
1052	133298
1053	133342
1054	133378
1055	133528
1056	133622
1057	133630
1058	133670
1059	133852
1060	133922
1061	134020
1062	134032
1063	134272
1064	134678
1065	134962
1066	135118
1067	135230
1068	135268
1069	135308
1070	135430
1071	135482
1072	135550
1073	135710
1074	135730
1075	135998
1076	136622
1077	136712
1078	136742
1079	136822
1080	136850
1081	137270
1082	137308
1083	137332
1084	137852
1085	138058
1086	138208
1087	138250
1088	138368
1089	138380
1090	138778
1091	138788
1092	138862
1093	139090
1094	139208
1095	139252
1096	139370
1097	139528
1098	139612
1099	139648
1100	139972
1101	140020
1102	140072
1103	140098
1104	140330
1105	140428
1106	140450
1107	140548
1108	140600
1109	140702
1110	140750
1111	140792
1112	141020
1113	141028
1114	141110
1115	141140
1116	141158
1117	141208
1118	141232
1119	141328
1120	141350
1121	141430
1122	141478
1123	141580
1124	141622
1125	141650
1126	141700
1127	142078
1128	142222
1129	142262
1130	142340
1131	142570
1132	142732
1133	142790
1134	142808
1135	142958
1136	143102
1137	143282
1138	143428
1139	143828
1140	143858
1141	144340
1142	144532
1143	144538
1144	144808
1145	144862
1146	144910
1147	145250
1148	145378
1149	145628
1150	145630
1151	145850
1152	145960
1153	146002
1154	146108
1155	146272
1156	146420
1157	146570
1158	146668
1159	146728
1160	146818
1161	146882
1162	146912
1163	146990
1164	147182
1165	147260
1166	147508
1167	147560
1168	147730
1169	147862
1170	148000
1171	148268
1172	148348
1173	148552
1174	148568
1175	148580
1176	148802
1177	148850
1178	148880
1179	149068
1180	149150
1181	149162
1182	149452
1183	149470
1184	149762
1185	149900
1186	149980
1187	150058
1188	150220
1189	150392
1190	150868
1191	151108
1192	151258
1193	151528
1194	151658
1195	151672
1196	152030
1197	152122
1198	152200
1199	152338
1200	152450
1201	152540
1202	152722
1203	152962
1204	153112
1205	153278
1206	153430
1207	153500
1208	153542
1209	153548
1210	154480
1211	154600
1212	155012
1213	155192
1214	155320
1215	155492
1216	155510
1217	155620
1218	155722
1219	155818
1220	155828
1221	155848
1222	155882
1223	155932
1224	156050
1225	156310
1226	156502
1227	156572
1228	156700
1229	156718
1230	156848
1231	156902
1232	156908
1233	157258
1234	157328
1235	157390
1236	157460
1237	157568
1238	157820
1239	157912
1240	157942
1241	157952
1242	158128
1243	158168
1244	158252
1245	158260
1246	158440
1247	158660
1248	158668
1249	158920
1250	158960
1251	159658
1252	159670
1253	160340
1254	160618
1255	160820
1256	161092
1257	161252
1258	161360
1259	161450
1260	161462
1261	161468
1262	161720
1263	161770
1264	161822
1265	161900
1266	161992
1267	162002
1268	162238
1269	162248
1270	162722
1271	162902
1272	163058
1273	163340
1274	163480
1275	163550
1276	163580
1277	163592
1278	163982
1279	164018
1280	164032
1281	164162
1282	164398
1283	164558
1284	164738
1285	164740
1286	164758
1287	165100
1288	165442
1289	165578
1290	165620
1291	165812
1292	165922
1293	165998
1294	166052
1295	166180
1296	166388
1297	166408
1298	166912
1299	167078
1300	167150
1301	167230
1302	167462
1303	167890
1304	167998
1305	168098
1306	168232
1307	168358
1308	168542
1309	168608
1310	168632
1311	168718
1312	168808
1313	169040
1314	169250
1315	169330
1316	169450
1317	169648
1318	169712
1319	169922
1320	170018
1321	170050
1322	170188
1323	170302
1324	170348
1325	170362
1326	170432
1327	170770
1328	171002
1329	171310
1330	171328
1331	171352
1332	171370
1333	171590
1334	171610
1335	171662
1336	171688
1337	171728
1338	171832
1339	172202
1340	172228
1341	172312
1342	172592
1343	172778
1344	172852
1345	172892
1346	172948
1347	172988
1348	173068
1349	173090
1350	173110
1351	173368
1352	173378
1353	173612
1354	173758
1355	173800
1356	173852
1357	174088
1358	174340
1359	174590
1360	174770
1361	174860
1362	174872
1363	174878
1364	174898
1365	174938
1366	175028
1367	175072
1368	175438
1369	175550
1370	175672
1371	175810
1372	175882
1373	176330
1374	176498
1375	176590
1376	176608
1377	176788
1378	176830
1379	176890
1380	176960
1381	177128
1382	177200
1383	177268
1384	177280
1385	177532
1386	177622
1387	177632
1388	177640
1389	177650
1390	177928
1391	177940
1392	178240
1393	178532
1394	178798
1395	178840
1396	178880
1397	178942
1398	179038
1399	179530
1400	179630
1401	180092
1402	180142
1403	180188
1404	180328
1405	180352
1406	180410
1407	180412
1408	180572
1409	180760
1410	180818
1411	181102
1412	181592
1413	181600
1414	182048
1415	182360
1416	182402
1417	182432
1418	182548
1419	182978
1420	183040
1421	183442
1422	183508
1423	183532
1424	183560
1425	183568
1426	183668
1427	183832
1428	183880
1429	183898
1430	184072
1431	184120
1432	184202
1433	184222
1434	184418
1435	184858
1436	185038
1437	185302
1438	185318
1439	185368
1440	185548
1441	185852
1442	186142
1443	186212
1444	186448
1445	186590
1446	186890
1447	187072
1448	187280
1449	187330
1450	187342
1451	187468
1452	187498
1453	187582
1454	187858
1455	187942
1456	188030
1457	188150
1458	188222
1459	188230
1460	188762
1461	188908
1462	188912
1463	189028
1464	189158
1465	189382
1466	189412
1467	189662
1468	189778
1469	189928
1470	190060
1471	190240
1472	190372
1473	190408
1474	190432
1475	190732
1476	191062
1477	191170
1478	191212
1479	191242
1480	191452
1481	191518
1482	192310
1483	192320
1484	192322
1485	192608
1486	192752
1487	192892
1488	193162
1489	193418
1490	193630
1491	193682
1492	193738
1493	193808
1494	194020
1495	194042
1496	194312
1497	194882
1498	195062
1499	195328
1500	195478
1501	195970
1502	195988
1503	196018
1504	196468
1505	196508
1506	196510
1507	196700
1508	196750
1509	196838
1510	197228
1511	197312
1512	197618
1513	197722
1514	197848
1515	197908
1516	197950
1517	198032
1518	198082
1519	198248
1520	198422
1521	198658
1522	198860
1523	199352
1524	199748