1	1
2	7
3	10
4	13
5	19
6	23
7	28
8	31
9	32
10	44
11	49
12	68
13	70
14	79
15	82
16	86
17	91
18	94
19	97
20	100
21	103
22	109
23	129
24	130
25	133
26	139
27	167
28	176
29	188
30	190
31	192
32	193
33	203
34	208
35	219
36	226
37	230
38	236
39	239
40	262
41	263
42	280
43	291
44	293
45	301
46	302
47	310
48	313
49	319
50	320
51	326
52	329
53	331
54	338
55	356
56	362
57	365
58	367
59	368
60	376
61	379
62	383
63	386
64	391
65	392
66	397
67	404
68	409
69	440
70	446
71	464
72	469
73	478
74	487
75	490
76	496
77	536
78	556
79	563
80	565
81	566
82	608
83	617
84	622
85	623
86	632
87	635
88	637
89	638
90	644
91	649
92	653
93	655
94	656
95	665
96	671
97	673
98	680
99	683
100	694
101	700
102	709
103	716
104	736
105	739
106	748
107	761
108	763
109	784
110	790
111	793
112	802
113	806
114	818
115	820
116	833
117	836
118	847
119	860
120	863
121	874
122	881
123	888
124	899
125	901
126	904
127	907
128	910
129	912
130	913
131	921
132	923
133	931
134	932
135	937
136	940
137	946
138	964
139	970
140	973
141	989
142	998
143	1000
144	1003
145	1009
146	1029
147	1030
148	1033
149	1039
150	1067
151	1076
152	1088
153	1090
154	1092
155	1093
156	1112
157	1114
158	1115
159	1121
160	1122
161	1125
162	1128
163	1141
164	1148
165	1151
166	1152
167	1158
168	1177
169	1182
170	1184
171	1185
172	1188
173	1209
174	1211
175	1212
176	1215
177	1218
178	1221
179	1222
180	1233
181	1247
182	1251
183	1257
184	1258
185	1274
186	1275
187	1277
188	1281
189	1285
190	1288
191	1290
192	1299
193	1300
194	1303
195	1309
196	1323
197	1330
198	1332
199	1333
200	1335
201	1337
202	1339
203	1353
204	1366
205	1373
206	1390
207	1393
208	1411
209	1418
210	1427
211	1444
212	1447
213	1448
214	1457
215	1472
216	1474
217	1475
218	1478
219	1481
220	1484
221	1487
222	1511
223	1512
224	1518
225	1521
226	1527
227	1528
228	1533
229	1547
230	1557
231	1572
232	1574
233	1575
234	1578
235	1581
236	1582
237	1587
238	1599
239	1607
240	1636
241	1663
242	1666
243	1670
244	1679
245	1697
246	1706
247	1717
248	1724
249	1725
250	1727
251	1733
252	1742
253	1744
254	1745
255	1748
256	1752
257	1754
258	1755
259	1758
260	1760
261	1769
262	1771
263	1772
264	1784
265	1785
266	1796
267	1808
268	1812
269	1814
270	1815
271	1818
272	1821
273	1825
274	1828
275	1841
276	1844
277	1847
278	1851
279	1852
280	1857
281	1874
282	1875
283	1880
284	1881
285	1882
286	1888
287	1900
288	1902
289	1903
290	1920
291	1929
292	1930
293	1933
294	1959
295	1967
296	1976
297	1992
298	1995
299	2003
300	2008
301	2019
302	2026
303	2030
304	2036
305	2039
306	2062
307	2063
308	2080
309	2091
310	2093
311	2109
312	2111
313	2112
314	2115
315	2118
316	2121
317	2122
318	2133
319	2147
320	2151
321	2157
322	2158
323	2174
324	2175
325	2177
326	2181
327	2185
328	2188
329	2190
330	2199
331	2206
332	2211
333	2212
334	2221
335	2224
336	2242
337	2245
338	2254
339	2257
340	2258
341	2260
342	2275
343	2285
344	2300
345	2306
346	2309
347	2313
348	2331
349	2333
350	2338
351	2339
352	2360
353	2369
354	2383
355	2390
356	2393
357	2396
358	2417
359	2422
360	2425
361	2448
362	2452
363	2455
364	2457
365	2458
366	2471
367	2475
368	2478
369	2484
370	2485
371	2487
372	2511
373	2517
374	2518
375	2524
376	2527
377	2528
378	2542
379	2545
380	2547
381	2548
382	2554
383	2555
384	2557
385	2568
386	2571
387	2572
388	2574
389	2575
390	2581
391	2582
392	2584
393	2586
394	2602
395	2603
396	2620
397	2630
398	2639
399	2658
400	2685
401	2693
402	2714
403	2715
404	2717
405	2725
406	2741
407	2745
408	2748
409	2751
410	2752
411	2754
412	2755
413	2771
414	2784
415	2800
416	2811
417	2815
418	2818
419	2825
420	2833
421	2844
422	2845
423	2847
424	2851
425	2852
426	2854
427	2856
428	2865
429	2874
430	2881
431	2899
432	2901
433	2903
434	2910
435	2919
436	2930
437	2933
438	2936
439	2963
440	2989
441	2991
442	2998
443	3001
444	3002
445	3010
446	3013
447	3019
448	3020
449	3026
450	3029
451	3031
452	3038
453	3056
454	3062
455	3065
456	3067
457	3068
458	3076
459	3079
460	3083
461	3086
462	3091
463	3092
464	3097
465	3100
466	3103
467	3109
468	3123
469	3130
470	3132
471	3133
472	3135
473	3137
474	3139
475	3153
476	3166
477	3173
478	3190
479	3193
480	3200
481	3206
482	3209
483	3213
484	3231
485	3233
486	3238
487	3239
488	3260
489	3269
490	3283
491	3290
492	3293
493	3296
494	3301
495	3308
496	3310
497	3312
498	3313
499	3315
500	3317
501	3319
502	3321
503	3323
504	3328
505	3329
506	3331
507	3332
508	3338
509	3346
510	3351
511	3355
512	3356
513	3364
514	3365
515	3367
516	3371
517	3376
518	3380
519	3382
520	3383
521	3391
522	3392
523	3436
524	3456
525	3463
526	3465
527	3466
528	3506
529	3513
530	3531
531	3535
532	3536
533	3546
534	3553
535	3560
536	3563
537	3564
538	3602
539	3605
540	3607
541	3608
542	3616
543	3620
544	3629
545	3634
546	3635
547	3637
548	3643
549	3645
550	3646
551	3650
552	3653
553	3654
554	3661
555	3664
556	3667
557	3670
558	3673
559	3676
560	3680
561	3689
562	3692
563	3698
564	3706
565	3709
566	3713
567	3731
568	3736
569	3760
570	3763
571	3766
572	3779
573	3789
574	3790
575	3797
576	3798
577	3803
578	3806
579	3823
580	3830
581	3832
582	3833
583	3860
584	3869
585	3879
586	3896
587	3897
588	3901
589	3902
590	3907
591	3910
592	3913
593	3920
594	3923
595	3926
596	3931
597	3932
598	3962
599	3968
600	3970
601	3977
602	3978
603	3986
604	3987
605	4004
606	4009
607	4040
608	4046
609	4064
610	4069
611	4078
612	4087
613	4090
614	4096
615	4111
616	4118
617	4127
618	4144
619	4147
620	4148
621	4157
622	4172
623	4174
624	4175
625	4178
626	4181
627	4184
628	4187
629	4217
630	4222
631	4225
632	4248
633	4252
634	4255
635	4257
636	4258
637	4271
638	4275
639	4278
640	4284
641	4285
642	4287
643	4336
644	4356
645	4363
646	4365
647	4366
648	4400
649	4406
650	4414
651	4417
652	4418
653	4428
654	4441
655	4447
656	4449
657	4455
658	4460
659	4471
660	4474
661	4477
662	4481
663	4482
664	4494
665	4517
666	4522
667	4525
668	4527
669	4528
670	4536
671	4545
672	4552
673	4554
674	4555
675	4558
676	4563
677	4571
678	4572
679	4577
680	4582
681	4585
682	4599
683	4604
684	4609
685	4633
686	4635
687	4636
688	4640
689	4653
690	4663
691	4690
692	4708
693	4712
694	4714
695	4715
696	4718
697	4721
698	4725
699	4728
700	4741
701	4744
702	4747
703	4751
704	4752
705	4757
706	4774
707	4775
708	4780
709	4781
710	4782
711	4788
712	4807
713	4811
714	4814
715	4817
716	4824
717	4825
718	4827
719	4841
720	4842
721	4852
722	4855
723	4870
724	4871
725	4872
726	4878
727	4887
728	4888
729	4900
730	4906
731	4944
732	4959
733	4960
734	4995
735	5036
736	5056
737	5063
738	5065
739	5066
740	5111
741	5112
742	5118
743	5121
744	5127
745	5128
746	5133
747	5147
748	5157
749	5172
750	5174
751	5175
752	5178
753	5181
754	5182
755	5187
756	5199
757	5211
758	5217
759	5218
760	5224
761	5227
762	5228
763	5242
764	5245
765	5247
766	5248
767	5254
768	5255
769	5257
770	5268
771	5271
772	5272
773	5274
774	5275
775	5281
776	5282
777	5284
778	5286
779	5306
780	5313
781	5331
782	5335
783	5336
784	5346
785	5353
786	5360
787	5363
788	5364
789	5417
790	5422
791	5425
792	5427
793	5428
794	5436
795	5445
796	5452
797	5454
798	5455
799	5458
800	5463
801	5471
802	5472
803	5477
804	5482
805	5485
806	5499
807	5506
808	5517
809	5524
810	5525
811	5527
812	5533
813	5542
814	5544
815	5545
816	5548
817	5552
818	5554
819	5555
820	5558
821	5560
822	5569
823	5571
824	5572
825	5584
826	5585
827	5596
828	5603
829	5605
830	5606
831	5628
832	5630
833	5633
834	5634
835	5643
836	5650
837	5659
838	5660
839	5666
840	5682
841	5695
842	5712
843	5714
844	5715
845	5718
846	5721
847	5722
848	5724
849	5725
850	5741
851	5742
852	5747
853	5751
854	5752
855	5774
856	5781
857	5789
858	5798
859	5799
860	5811
861	5812
862	5817
863	5821
864	5822
865	5824
866	5826
867	5842
868	5845
869	5854
870	5855
871	5862
872	5871
873	5879
874	5897
875	5919
876	5949
877	5956
878	5965
879	5978
880	5979
881	5987
882	5991
883	5994
884	5997
885	6008
886	6017
887	6022
888	6023
889	6032
890	6035
891	6037
892	6038
893	6044
894	6049
895	6053
896	6055
897	6056
898	6065
899	6071
900	6073
901	6080
902	6083
903	6094
904	6107
905	6136
906	6163
907	6166
908	6170
909	6179
910	6197
911	6202
912	6203
913	6220
914	6230
915	6239
916	6258
917	6285
918	6293
919	6302
920	6305
921	6307
922	6308
923	6316
924	6320
925	6329
926	6334
927	6335
928	6337
929	6343
930	6345
931	6346
932	6350
933	6353
934	6354
935	6361
936	6364
937	6367
938	6370
939	6373
940	6376
941	6380
942	6389
943	6392
944	6398
945	6404
946	6409
947	6433
948	6435
949	6436
950	6440
951	6453
952	6463
953	6490
954	6503
955	6505
956	6506
957	6528
958	6530
959	6533
960	6534
961	6543
962	6550
963	6559
964	6560
965	6566
966	6582
967	6595
968	6605
969	6613
970	6616
971	6631
972	6634
973	6637
974	6643
975	6650
976	6656
977	6661
978	6665
979	6673
980	6701
981	6703
982	6710
983	6719
984	6730
985	6733
986	6736
987	6763
988	6789
989	6791
990	6798
991	6800
992	6803
993	6825
994	6830
995	6839
996	6852
997	6879
998	6893
999	6897
1000	6899
1001	6904
1002	6917
1003	6923
1004	6932
1005	6938
1006	6940
1007	6955
1008	6971
1009	6978
1010	6983
1011	6987
1012	6989
1013	6998
1014	7000
1015	7009
1016	7016
1017	7036
1018	7039
1019	7048
1020	7061
1021	7063
1022	7084
1023	7090
1024	7093
1025	7106
1026	7117
1027	7124
1028	7125
1029	7127
1030	7133
1031	7142
1032	7144
1033	7145
1034	7148
1035	7152
1036	7154
1037	7155
1038	7158
1039	7160
1040	7169
1041	7171
1042	7172
1043	7184
1044	7185
1045	7196
1046	7214
1047	7215
1048	7217
1049	7225
1050	7241
1051	7245
1052	7248
1053	7251
1054	7252
1055	7254
1056	7255
1057	7271
1058	7284
1059	7306
1060	7309
1061	7313
1062	7331
1063	7336
1064	7360
1065	7363
1066	7366
1067	7379
1068	7389
1069	7390
1070	7397
1071	7398
1072	7408
1073	7412
1074	7414
1075	7415
1076	7418
1077	7421
1078	7425
1079	7428
1080	7441
1081	7444
1082	7447
1083	7451
1084	7452
1085	7457
1086	7474
1087	7475
1088	7480
1089	7481
1090	7482
1091	7488
1092	7512
1093	7514
1094	7515
1095	7518
1096	7521
1097	7522
1098	7524
1099	7525
1100	7541
1101	7542
1102	7547
1103	7551
1104	7552
1105	7574
1106	7581
1107	7589
1108	7598
1109	7599
1110	7601
1111	7603
1112	7610
1113	7619
1114	7630
1115	7633
1116	7636
1117	7663
1118	7689
1119	7691
1120	7698
1121	7711
1122	7712
1123	7721
1124	7739
1125	7744
1126	7745
1127	7754
1128	7788
1129	7793
1130	7804
1131	7814
1132	7815
1133	7824
1134	7839
1135	7840
1136	7841
1137	7842
1138	7848
1139	7851
1140	7859
1141	7869
1142	7878
1143	7884
1144	7887
1145	7893
1146	7895
1147	7896
1148	7900
1149	7903
1150	7916
1151	7930
1152	7937
1153	7938
1154	7958
1155	7959
1156	7961
1157	7968
1158	7973
1159	7983
1160	7985
1161	7986
1162	7995
1163	8002
1164	8006
1165	8018
1166	8020
1167	8033
1168	8036
1169	8047
1170	8060
1171	8063
1172	8074
1173	8081
1174	8088
1175	8099
1176	8108
1177	8112
1178	8114
1179	8115
1180	8118
1181	8121
1182	8125
1183	8128
1184	8141
1185	8144
1186	8147
1187	8151
1188	8152
1189	8157
1190	8174
1191	8175
1192	8180
1193	8181
1194	8182
1195	8188
1196	8200
1197	8211
1198	8215
1199	8218
1200	8225
1201	8233
1202	8244
1203	8245
1204	8247
1205	8251
1206	8252
1207	8254
1208	8256
1209	8265
1210	8274
1211	8281
1212	8299
1213	8303
1214	8306
1215	8323
1216	8330
1217	8332
1218	8333
1219	8360
1220	8369
1221	8379
1222	8396
1223	8397
1224	8407
1225	8411
1226	8414
1227	8417
1228	8424
1229	8425
1230	8427
1231	8441
1232	8442
1233	8452
1234	8455
1235	8470
1236	8471
1237	8472
1238	8478
1239	8487
1240	8488
1241	8511
1242	8512
1243	8517
1244	8521
1245	8522
1246	8524
1247	8526
1248	8542
1249	8545
1250	8554
1251	8555
1252	8562
1253	8571
1254	8579
1255	8597
1256	8600
1257	8603
1258	8625
1259	8630
1260	8639
1261	8652
1262	8679
1263	8693
1264	8697
1265	8699
1266	8704
1267	8714
1268	8715
1269	8724
1270	8739
1271	8740
1272	8741
1273	8742
1274	8748
1275	8751
1276	8759
1277	8769
1278	8778
1279	8784
1280	8787
1281	8793
1282	8795
1283	8796
1284	8801
1285	8808
1286	8810
1287	8811
1288	8812
1289	8818
1290	8821
1291	8847
1292	8848
1293	8874
1294	8877
1295	8880
1296	8881
1297	8884
1298	8909
1299	8929
1300	8936
1301	8937
1302	8957
1303	8963
1304	8967
1305	8969
1306	8973
1307	8975
1308	8976
1309	8990
1310	8992
1311	8996
1312	9001
1313	9004
1314	9007
1315	9010
1316	9012
1317	9013
1318	9021
1319	9023
1320	9031
1321	9032
1322	9037
1323	9040
1324	9046
1325	9064
1326	9070
1327	9073
1328	9089
1329	9098
1330	9100
1331	9102
1332	9103
1333	9120
1334	9129
1335	9130
1336	9133
1337	9159
1338	9167
1339	9176
1340	9192
1341	9195
1342	9201
1343	9203
1344	9210
1345	9219
1346	9230
1347	9233
1348	9236
1349	9263
1350	9289
1351	9291
1352	9298
1353	9301
1354	9302
1355	9307
1356	9310
1357	9313
1358	9320
1359	9323
1360	9326
1361	9331
1362	9332
1363	9362
1364	9368
1365	9370
1366	9377
1367	9378
1368	9386
1369	9387
1370	9400
1371	9406
1372	9444
1373	9459
1374	9460
1375	9495
1376	9519
1377	9549
1378	9556
1379	9565
1380	9578
1381	9579
1382	9587
1383	9591
1384	9594
1385	9597
1386	9604
1387	9617
1388	9623
1389	9632
1390	9638
1391	9640
1392	9655
1393	9671
1394	9678
1395	9683
1396	9687
1397	9689
1398	9698
1399	9700
1400	9703
1401	9716
1402	9730
1403	9737
1404	9738
1405	9758
1406	9759
1407	9761
1408	9768
1409	9773
1410	9783
1411	9785
1412	9786
1413	9795
1414	9809
1415	9829
1416	9836
1417	9837
1418	9857
1419	9863
1420	9867
1421	9869
1422	9873
1423	9875
1424	9876
1425	9890
1426	9892
1427	9896
1428	9908
1429	9912
1430	9915
1431	9921
1432	9928
1433	9945
1434	9951
1435	9954
1436	9957
1437	9968
1438	9975
1439	9980
1440	9982
1441	9986
1442	10000