1	0
7	5
10	1
13	2
19	4
23	3
28	3
31	2
32	3
44	4
49	4
68	2
70	5
79	3
82	3
86	2
91	4
94	4
97	3
100	1
103	2
109	4
129	3
130	2
133	5
139	5
167	3
176	3
188	4
190	4
192	3
193	5
203	3
208	3
219	3
226	5
230	3
236	5
239	5
262	5
263	5
280	3
291	3
293	5
301	2
302	3
310	2
313	5
319	5
320	3
326	5
329	5
331	5
338	4
356	6
362	5
365	6
367	5
368	5
376	5
379	6
383	4
386	5
391	5
392	5
397	6
404	4
409	4
440	4
446	3
464	3
469	6
478	4
487	4
490	4
496	6
536	6
556	3
563	6
565	3
566	4
608	2
617	3
622	5
623	5
632	5
635	6
637	5
638	5
644	3
649	6
653	6
655	3
656	4
665	4
671	3
673	5
680	2
683	5
694	6
700	5
709	3
716	3
736	5
739	6
748	4
761	3
763	5
784	4
790	3
793	6
802	3
806	2
818	4
820	3
833	4
836	5
847	4
860	2
863	5
874	4
881	4
888	4
899	6
901	4
904	4
907	3
910	4
912	3
913	5
921	3
923	5
931	5
932	5
937	6
940	4
946	6
964	6
970	3
973	6
989	6
998	6
1000	1
1003	2
1009	4
1029	3
1030	2
1033	5
1039	5
1067	3
1076	3
1088	4
1090	4
1092	3
1093	5
1112	6
1114	5
1115	4
1121	6
1122	2
1125	3
1128	6
1141	5
1148	4
1151	4
1152	3
1158	5
1177	2
1182	6
1184	4
1185	5
1188	3
1209	3
1211	6
1212	2
1215	3
1218	6
1221	2
1222	3
1233	4
1247	6
1251	3
1257	4
1258	5
1274	6
1275	4
1277	3
1281	6
1285	5
1288	6
1290	3
1299	4
1300	2
1303	5
1309	5
1323	4
1330	5
1332	4
1333	4
1335	5
1337	3
1339	2
1353	5
1366	4
1373	3
1390	5
1393	2
1411	5
1418	4
1427	6
1444	5
1447	4
1448	4
1457	5
1472	6
1474	4
1475	5
1478	3
1481	4
1484	4
1487	3
1511	4
1512	3
1518	5
1521	3
1527	4
1528	5
1533	5
1547	5
1557	2
1572	4
1574	5
1575	2
1578	6
1581	5
1582	5
1587	6
1599	5
1607	3
1636	4
1663	4
1666	5
1670	3
1679	4
1697	4
1706	3
1717	2
1724	6
1725	4
1727	3
1733	3
1742	6
1744	4
1745	5
1748	3
1752	4
1754	5
1755	2
1758	6
1760	3
1769	4
1771	2
1772	3
1784	3
1785	6
1796	4
1808	4
1812	6
1814	4
1815	5
1818	3
1821	6
1825	5
1828	6
1841	4
1844	4
1847	3
1851	5
1852	5
1857	6
1874	3
1875	6
1880	4
1881	3
1882	6
1888	6
1900	4
1902	3
1903	5
1920	3
1929	4
1930	5
1933	2
1959	5
1967	4
1976	4
1992	4
1995	5
2003	3
2008	3
2019	3
2026	5
2030	3
2036	5
2039	5
2062	5
2063	5
2080	3
2091	3
2093	5
2109	3
2111	6
2112	2
2115	3
2118	6
2121	2
2122	3
2133	4
2147	6
2151	3
2157	4
2158	5
2174	6
2175	4
2177	3
2181	6
2185	5
2188	6
2190	3
2199	4
2206	5
2211	2
2212	3
2221	3
2224	4
2242	4
2245	5
2254	5
2257	4
2258	4
2260	5
2275	4
2285	4
2300	3
2306	5
2309	5
2313	4
2331	4
2333	3
2338	3
2339	3
2360	5
2369	3
2383	3
2390	5
2393	3
2396	3
2417	6
2422	4
2425	5
2448	2
2452	5
2455	6
2457	5
2458	5
2471	6
2475	5
2478	6
2484	2
2485	5
2487	6
2511	3
2517	4
2518	5
2524	5
2527	4
2528	4
2542	5
2545	6
2547	5
2548	5
2554	6
2555	4
2557	3
2568	4
2571	4
2572	4
2574	5
2575	3
2581	5
2582	4
2584	5
2586	4
2602	5
2603	5
2620	5
2630	5
2639	3
2658	4
2685	4
2693	3
2714	6
2715	4
2717	3
2725	4
2741	6
2745	5
2748	6
2751	4
2752	4
2754	5
2755	3
2771	3
2784	6
2800	3
2811	6
2815	5
2818	6
2825	4
2833	3
2844	2
2845	5
2847	6
2851	5
2852	4
2854	5
2856	4
2865	4
2874	6
2881	6
2899	4
2901	3
2903	5
2910	3
2919	4
2930	5
2933	3
2936	3
2963	3
2989	4
2991	4
2998	4
3001	2
3002	3
3010	2
3013	5
3019	5
3020	3
3026	5
3029	5
3031	5
3038	4
3056	6
3062	5
3065	6
3067	5
3068	5
3076	5
3079	6
3083	4
3086	5
3091	5
3092	5
3097	6
3100	2
3103	5
3109	5
3123	4
3130	5
3132	4
3133	4
3135	5
3137	3
3139	2
3153	5
3166	4
3173	3
3190	5
3193	2
3200	3
3206	5
3209	5
3213	4
3231	4
3233	3
3238	3
3239	3
3260	5
3269	3
3283	3
3290	5
3293	3
3296	3
3301	5
3308	4
3310	5
3312	4
3313	4
3315	5
3317	3
3319	2
3321	4
3323	3
3328	3
3329	3
3331	4
3332	3
3338	5
3346	6
3351	5
3355	3
3356	4
3364	6
3365	4
3367	3
3371	3
3376	3
3380	4
3382	3
3383	5
3391	2
3392	3
3436	6
3456	3
3463	6
3465	3
3466	4
3506	6
3513	5
3531	5
3535	3
3536	4
3546	3
3553	3
3560	6
3563	4
3564	3
3602	5
3605	6
3607	5
3608	5
3616	4
3620	5
3629	3
3634	6
3635	4
3637	3
3643	6
3645	3
3646	4
3650	6
3653	4
3654	3
3661	4
3664	4
3667	3
3670	5
3673	3
3676	3
3680	5
3689	5
3692	3
3698	5
3706	5
3709	6
3713	3
3731	3
3736	3
3760	5
3763	3
3766	3
3779	5
3789	4
3790	6
3797	5
3798	4
3803	4
3806	5
3823	3
3830	4
3832	3
3833	5
3860	5
3869	5
3879	4
3896	5
3897	4
3901	5
3902	5
3907	6
3910	5
3913	2
3920	5
3923	3
3926	3
3931	2
3932	3
3962	3
3968	5
3970	6
3977	5
3978	4
3986	5
3987	4
4004	4
4009	4
4040	4
4046	3
4064	3
4069	6
4078	4
4087	4
4090	4
4096	6
4111	5
4118	4
4127	6
4144	5
4147	4
4148	4
4157	5
4172	6
4174	4
4175	5
4178	3
4181	4
4184	4
4187	3
4217	6
4222	4
4225	5
4248	2
4252	5
4255	6
4257	5
4258	5
4271	6
4275	5
4278	6
4284	2
4285	5
4287	6
4336	6
4356	3
4363	6
4365	3
4366	4
4400	4
4406	3
4414	5
4417	4
4418	4
4428	2
4441	5
4447	4
4449	4
4455	4
4460	3
4471	4
4474	4
4477	3
4481	4
4482	2
4494	4
4517	5
4522	5
4525	6
4527	5
4528	5
4536	3
4545	4
4552	6
4554	4
4555	5
4558	3
4563	3
4571	5
4572	5
4577	6
4582	5
4585	3
4599	4
4604	3
4609	6
4633	6
4635	3
4636	4
4640	3
4653	3
4663	4
4690	6
4708	4
4712	6
4714	4
4715	5
4718	3
4721	6
4725	5
4728	6
4741	4
4744	4
4747	3
4751	5
4752	5
4757	6
4774	3
4775	6
4780	4
4781	3
4782	6
4788	6
4807	4
4811	4
4814	4
4817	3
4824	2
4825	5
4827	6
4841	4
4842	2
4852	5
4855	3
4870	4
4871	3
4872	6
4878	6
4887	6
4888	4
4900	4
4906	6
4944	4
4959	4
4960	6
4995	4
5036	6
5056	3
5063	6
5065	3
5066	4
5111	4
5112	3
5118	5
5121	3
5127	4
5128	5
5133	5
5147	5
5157	2
5172	4
5174	5
5175	2
5178	6
5181	5
5182	5
5187	6
5199	5
5211	3
5217	4
5218	5
5224	5
5227	4
5228	4
5242	5
5245	6
5247	5
5248	5
5254	6
5255	4
5257	3
5268	4
5271	4
5272	4
5274	5
5275	3
5281	5
5282	4
5284	5
5286	4
5306	6
5313	5
5331	5
5335	3
5336	4
5346	3
5353	3
5360	6
5363	4
5364	3
5417	5
5422	5
5425	6
5427	5
5428	5
5436	3
5445	4
5452	6
5454	4
5455	5
5458	3
5463	3
5471	5
5472	5
5477	6
5482	5
5485	3
5499	4
5506	3
5517	2
5524	6
5525	4
5527	3
5533	3
5542	6
5544	4
5545	5
5548	3
5552	4
5554	5
5555	2
5558	6
5560	3
5569	4
5571	2
5572	3
5584	3
5585	6
5596	4
5603	6
5605	3
5606	4
5628	4
5630	6
5633	4
5634	3
5643	3
5650	3
5659	4
5660	4
5666	6
5682	4
5695	4
5712	4
5714	5
5715	2
5718	6
5721	4
5722	4
5724	5
5725	3
5741	5
5742	5
5747	6
5751	2
5752	3
5774	6
5781	6
5789	4
5798	4
5799	6
5811	5
5812	5
5817	6
5821	5
5822	4
5824	5
5826	4
5842	5
5845	3
5854	3
5855	6
5862	4
5871	6
5879	4
5897	4
5919	5
5949	4
5956	4
5965	4
5978	4
5979	6
5987	4
5991	5
5994	4
5997	6
6008	2
6017	3
6022	5
6023	5
6032	5
6035	6
6037	5
6038	5
6044	3
6049	6
6053	6
6055	3
6056	4
6065	4
6071	3
6073	5
6080	2
6083	5
6094	6
6107	3
6136	4
6163	4
6166	5
6170	3
6179	4
6197	4
6202	5
6203	5
6220	5
6230	5
6239	3
6258	4
6285	4
6293	3
6302	5
6305	6
6307	5
6308	5
6316	4
6320	5
6329	3
6334	6
6335	4
6337	3
6343	6
6345	3
6346	4
6350	6
6353	4
6354	3
6361	4
6364	4
6367	3
6370	5
6373	3
6376	3
6380	5
6389	5
6392	3
6398	5
6404	3
6409	6
6433	6
6435	3
6436	4
6440	3
6453	3
6463	4
6490	6
6503	6
6505	3
6506	4
6528	4
6530	6
6533	4
6534	3
6543	3
6550	3
6559	4
6560	4
6566	6
6582	4
6595	4
6605	4
6613	4
6616	5
6631	4
6634	4
6637	3
6643	4
6650	4
6656	6
6661	5
6665	6
6673	3
6701	3
6703	5
6710	3
6719	4
6730	5
6733	3
6736	3
6763	3
6789	4
6791	4
6798	4
6800	2
6803	5
6825	4
6830	5
6839	5
6852	4
6879	4
6893	5
6897	4
6899	6
6904	6
6917	4
6923	3
6932	3
6938	5
6940	6
6955	4
6971	4
6978	4
6983	5
6987	4
6989	6
6998	6
7000	5
7009	3
7016	3
7036	5
7039	6
7048	4
7061	3
7063	5
7084	4
7090	3
7093	6
7106	3
7117	2
7124	6
7125	4
7127	3
7133	3
7142	6
7144	4
7145	5
7148	3
7152	4
7154	5
7155	2
7158	6
7160	3
7169	4
7171	2
7172	3
7184	3
7185	6
7196	4
7214	6
7215	4
7217	3
7225	4
7241	6
7245	5
7248	6
7251	4
7252	4
7254	5
7255	3
7271	3
7284	6
7306	5
7309	6
7313	3
7331	3
7336	3
7360	5
7363	3
7366	3
7379	5
7389	4
7390	6
7397	5
7398	4
7408	4
7412	6
7414	4
7415	5
7418	3
7421	6
7425	5
7428	6
7441	4
7444	4
7447	3
7451	5
7452	5
7457	6
7474	3
7475	6
7480	4
7481	3
7482	6
7488	6
7512	4
7514	5
7515	2
7518	6
7521	4
7522	4
7524	5
7525	3
7541	5
7542	5
7547	6
7551	2
7552	3
7574	6
7581	6
7589	4
7598	4
7599	6
7601	3
7603	5
7610	3
7619	4
7630	5
7633	3
7636	3
7663	3
7689	4
7691	4
7698	4
7711	2
7712	3
7721	3
7739	5
7744	3
7745	6
7754	6
7788	6
7793	5
7804	4
7814	3
7815	6
7824	6
7839	4
7840	4
7841	3
7842	6
7848	6
7851	6
7859	4
7869	4
7878	6
7884	6
7887	6
7893	4
7895	4
7896	4
7900	3
7903	6
7916	4
7930	6
7937	5
7938	4
7958	4
7959	6
7961	4
7968	4
7973	5
7983	4
7985	4
7986	4
7995	6
8002	3
8006	2
8018	4
8020	3
8033	4
8036	5
8047	4
8060	2
8063	5
8074	4
8081	4
8088	4
8099	6
8108	4
8112	6
8114	4
8115	5
8118	3
8121	6
8125	5
8128	6
8141	4
8144	4
8147	3
8151	5
8152	5
8157	6
8174	3
8175	6
8180	4
8181	3
8182	6
8188	6
8200	3
8211	6
8215	5
8218	6
8225	4
8233	3
8244	2
8245	5
8247	6
8251	5
8252	4
8254	5
8256	4
8265	4
8274	6
8281	6
8299	4
8303	4
8306	5
8323	3
8330	4
8332	3
8333	5
8360	5
8369	5
8379	4
8396	5
8397	4
8407	4
8411	4
8414	4
8417	3
8424	2
8425	5
8427	6
8441	4
8442	2
8452	5
8455	3
8470	4
8471	3
8472	6
8478	6
8487	6
8488	4
8511	5
8512	5
8517	6
8521	5
8522	4
8524	5
8526	4
8542	5
8545	3
8554	3
8555	6
8562	4
8571	6
8579	4
8597	4
8600	2
8603	5
8625	4
8630	5
8639	5
8652	4
8679	4
8693	5
8697	4
8699	6
8704	4
8714	3
8715	6
8724	6
8739	4
8740	4
8741	3
8742	6
8748	6
8751	6
8759	4
8769	4
8778	6
8784	6
8787	6
8793	4
8795	4
8796	4
8801	4
8808	4
8810	4
8811	3
8812	6
8818	6
8821	6
8847	6
8848	4
8874	6
8877	6
8880	4
8881	6
8884	4
8909	6
8929	4
8936	5
8937	4
8957	4
8963	5
8967	4
8969	6
8973	4
8975	4
8976	4
8990	6
8992	4
8996	6
9001	4
9004	4
9007	3
9010	4
9012	3
9013	5
9021	3
9023	5
9031	5
9032	5
9037	6
9040	4
9046	6
9064	6
9070	3
9073	6
9089	6
9098	6
9100	4
9102	3
9103	5
9120	3
9129	4
9130	5
9133	2
9159	5
9167	4
9176	4
9192	4
9195	5
9201	3
9203	5
9210	3
9219	4
9230	5
9233	3
9236	3
9263	3
9289	4
9291	4
9298	4
9301	5
9302	5
9307	6
9310	5
9313	2
9320	5
9323	3
9326	3
9331	2
9332	3
9362	3
9368	5
9370	6
9377	5
9378	4
9386	5
9387	4
9400	4
9406	6
9444	4
9459	4
9460	6
9495	4
9519	5
9549	4
9556	4
9565	4
9578	4
9579	6
9587	4
9591	5
9594	4
9597	6
9604	6
9617	4
9623	3
9632	3
9638	5
9640	6
9655	4
9671	4
9678	4
9683	5
9687	4
9689	6
9698	6
9700	3
9703	6
9716	4
9730	6
9737	5
9738	4
9758	4
9759	6
9761	4
9768	4
9773	5
9783	4
9785	4
9786	4
9795	6
9809	6
9829	4
9836	5
9837	4
9857	4
9863	5
9867	4
9869	6
9873	4
9875	4
9876	4
9890	6
9892	4
9896	6
9908	6
9912	4
9915	5
9921	4
9928	4
9945	4
9951	5
9954	4
9957	6
9968	6
9975	6
9980	6
9982	4
9986	6
10000	1