1	0
2	1
3	1
4	1
5	1
6	1
7	1
8	1
9	1
10	1
11	2
12	1
13	1
14	1
15	1
16	1
17	1
18	2
19	1
20	2
21	2
22	1
23	2
24	1
25	2
26	1
27	1
28	2
29	3
30	1
31	1
32	1
33	1
34	1
35	2
36	2
37	2
38	1
39	2
40	1
41	2
42	1
43	3
44	2
45	2
46	1
47	3
48	2
49	1
50	2
51	3
52	3
53	3
54	2
55	3
56	1
57	2
58	2
59	2
60	2
61	1
62	1
63	2
64	2
65	1
66	2
67	2
68	3
69	1
70	2
71	3
72	2
73	3
74	2
75	2
76	3
77	1
78	1
79	3
80	1
81	3
82	2
83	2
84	2
85	1
86	1
87	2
88	2
89	1
90	1
91	3
92	4
93	1
94	2
95	3
96	2
97	2
98	1
99	3
100	4
101	2
102	3
103	2
104	2
105	3
106	2
107	1
108	2
109	2
110	3
111	3
112	2
113	5
114	2
115	3
116	2
117	4
118	3
119	4
120	1
121	2
122	1
123	2
124	4
125	2
126	1
127	1
128	2
129	1
130	3
131	2
132	2
133	1
134	2
135	3
136	3
137	2
138	2
139	2
140	2
141	2
142	2
143	3
144	2
145	1
146	2
147	2
148	4
149	2
150	1
151	5
152	3
153	2
154	3
155	6
156	5
157	4
158	1
159	4
160	2
161	4
162	4
163	5
164	4
165	1
166	5
167	2
168	2
169	3
170	1
171	2
172	4
173	4
174	1
175	3
176	3
177	3
178	3
179	3
180	3
181	4
182	3
183	3
184	1
185	2
186	2
187	2
188	3
189	2
190	2
191	5
192	1
193	3
194	4
195	1
196	3
197	2
198	2
199	2
200	4
201	3
202	1
203	3
204	4
205	3
206	2
207	4
208	1
209	3
210	3
211	3
212	3
213	3
214	2
215	4
216	2
217	4
218	2
219	3
220	2
221	2
222	3
223	6
224	4
225	4
226	4
227	2
228	3
229	4
230	3
231	2
232	2
233	4
234	1
235	3
236	6
237	4
238	2
239	6
240	2
241	2
242	2
243	4
244	5
245	2
246	3
247	4
248	3
249	2
250	2
251	5
252	2
253	4
254	1
255	3
256	2
257	3
258	3
259	2
260	4
261	1
262	3
263	4
264	3
265	3
266	2
267	3
268	5
269	2
270	3
271	2
272	3
273	3
274	4
275	2
276	2
277	3
278	2
279	5
280	1
281	2
282	3
283	3
284	5
285	2
286	4
287	2
288	4
289	3
290	2
291	4
292	4
293	2
294	2
295	7
296	1
297	2
298	4
299	6
300	4
301	3
302	2
303	2
304	3
305	6
306	3
307	5
308	4
309	2
310	3
311	3
312	1
313	4
314	4
315	3
316	3
317	4
318	2
319	4
320	2
321	2
322	1
323	4
324	4
325	3
326	3
327	3
328	3
329	5
330	2
331	3
332	5
333	8
334	1
335	3
336	3
337	5
338	2
339	3
340	5
341	3
342	2
343	4
344	3
345	1
346	5
347	2
348	4
349	3
350	4
351	5
352	2
353	3
354	3
355	2
356	3
357	3
358	2
359	6
360	2
361	3
362	3
363	4
364	5
365	4
366	1
367	5
368	3
369	2
370	3
371	5
372	3
373	2
374	1
375	2
376	4
377	4
378	4
379	2
380	4
381	4
382	1
383	5
384	2
385	3
386	5
387	4
388	8
389	3
390	2
391	3
392	6
393	4
394	3
395	4
396	4
397	9
398	1
399	3
400	4
401	4
402	4
403	3
404	5
405	3
406	3
407	4
408	4
409	3
410	1
411	4
412	5
413	3
414	1
415	5
416	5
417	2
418	3
419	5
420	3
421	2
422	5
423	2
424	3
425	1
426	4
427	2
428	5
429	3
430	2
431	8
432	3
433	4
434	2
435	2
436	5
437	4
438	2
439	4
440	5
441	5
442	3
443	3
444	4
445	3
446	2
447	1
448	2
449	5
450	2
451	5
452	4
453	2
454	3
455	2
456	3
457	2
458	2
459	3
460	6
461	4
462	2
463	6
464	5
465	3
466	3
467	3
468	5
469	3
470	3
471	1
472	5
473	5
474	3
475	5
476	6
477	4
478	3
479	4
480	2
481	3
482	4
483	5
484	4
485	4
486	5
487	2
488	4
489	5
490	3
491	7
492	4
493	3
494	4
495	3
496	2
497	3
498	2
499	3
500	7
501	2
502	2
503	4
504	5
505	2
506	5
507	1
508	8
509	4
510	3
511	3
512	2
513	5
514	3
515	4
516	4
517	6
518	2
519	2
520	5
521	1
522	4
523	2
524	6
525	4
526	4
527	3
528	2
529	4
530	2
531	6
532	5
533	3
534	3
535	6
536	3
537	4
538	2
539	2
540	5
541	5
542	4
543	3
544	3
545	6
546	3
547	4
548	4
549	3
550	1
551	4
552	2
553	2
554	2
555	2
556	6
557	5
558	4
559	3
560	4
561	3
562	3
563	3
564	6
565	3
566	5
567	1
568	3
569	5
570	2
571	4
572	6
573	2
574	4
575	3
576	4
577	3
578	6
579	1
580	5
581	4
582	4
583	4
584	2
585	4
586	5
587	6
588	3
589	4
590	1
591	4
592	2
593	4
594	4
595	4
596	5
597	3
598	3
599	3
600	1
601	4
602	2
603	2
604	3
605	3
606	2
607	1
608	6
609	2
610	3
611	3
612	6
613	3
614	4
615	5
616	3
617	4
618	7
619	4
620	6
621	3
622	2
623	3
624	3
625	4
626	1
627	5
628	4
629	3
630	2
631	3
632	3
633	5
634	3
635	3
636	4
637	8
638	4
639	5
640	5
641	6
642	4
643	3
644	8
645	5
646	4
647	3
648	7
649	4
650	5
651	3
652	6
653	6
654	3
655	5
656	4
657	7
658	3
659	4
660	6
661	5
662	5
663	3
664	3
665	2
666	4
667	6
668	4
669	2
670	2
671	5
672	2
673	4
674	4
675	4
676	6
677	5
678	3
679	5
680	5
681	2
682	4
683	3
684	6
685	4
686	3
687	4
688	2
689	4
690	1
691	5
692	4
693	3
694	1
695	5
696	4
697	2
698	2
699	4
700	3
701	8
702	2
703	6
704	4
705	2
706	2
707	6
708	7
709	3
710	2
711	5
712	1
713	4
714	2
715	3
716	5
717	6
718	4
719	4
720	2
721	2
722	2
723	4
724	6
725	5
726	3
727	2
728	2
729	5
730	3
731	3
732	5
733	4
734	6
735	6
736	3
737	6
738	4
739	4
740	6
741	3
742	4
743	7
744	4
745	1
746	3
747	2
748	7
749	6
750	3
751	3
752	6
753	5
754	2
755	4
756	3
757	4
758	3
759	3
760	2
761	5
762	3
763	2
764	6
765	5
766	3
767	7
768	2
769	3
770	3
771	2
772	7
773	6
774	2
775	4
776	2
777	5
778	4
779	8
780	5
781	5
782	6
783	4
784	5
785	5
786	3
787	4
788	6
789	6
790	3
791	4
792	2
793	6
794	5
795	1
796	4
797	7
798	3
799	3
800	3
801	6
802	4
803	6
804	8
805	3
806	5
807	3
808	2
809	2
810	7
811	4
812	4
813	6
814	5
815	3
816	1
817	5
818	3
819	3
820	7
821	5
822	4
823	4
824	6
825	4
826	3
827	6
828	9
829	3
830	3
831	6
832	3
833	5
834	4
835	4
836	7
837	2
838	3
839	5
840	4
841	2
842	3
843	3
844	4
845	3
846	3
847	2
848	2
849	5
850	3
851	3
852	8
853	5
854	3
855	3
856	4
857	4
858	3
859	4
860	7
861	3
862	3
863	5
864	2
865	2
866	2
867	2
868	4
869	3
870	4
871	6
872	4
873	4
874	5
875	2
876	6
877	6
878	5
879	8
880	4
881	2
882	6
883	4
884	5
885	2
886	5
887	5
888	6
889	2
890	4
891	3
892	7
893	3
894	2
895	6
896	2
897	1
898	4
899	5
900	5
901	3
902	4
903	2
904	3
905	4
906	5
907	4
908	7
909	1
910	5
911	4
912	3
913	3
914	2
915	4
916	9
917	8
918	5
919	3
920	2
921	4
922	6
923	4
924	2
925	3
926	4
927	7
928	6
929	5
930	4
931	4
932	6
933	5
934	7
935	4
936	4
937	5
938	4
939	5
940	8
941	3
942	5
943	8
944	2
945	2
946	5
947	6
948	4
949	8
950	3
951	4
952	5
953	6
954	1
955	5
956	3
957	3
958	5
959	6
960	5
961	3
962	3
963	3
964	5
965	5
966	2
967	5
968	5
969	5
970	2
971	2
972	6
973	4
974	2
975	5
976	2
977	6
978	2
979	4
980	5
981	7
982	3
983	2
984	2
985	5
986	4
987	3
988	6
989	4
990	1
991	5
992	6
993	5
994	4
995	6
996	7
997	2
998	6
999	4
1000	6
1001	4
1002	4
1003	4
1004	8
1005	3
1006	2
1007	4
1008	2
1009	8
1010	8
1011	3
1012	9
1013	4
1014	3
1015	2
1016	6
1017	3
1018	3
1019	5
1020	6
1021	5
1022	5
1023	3
1024	3
1025	8
1026	3
1027	5
1028	5
1029	6
1030	3
1031	4
1032	5
1033	5
1034	6
1035	3
1036	4
1037	3
1038	2
1039	3
1040	5
1041	2
1042	4
1043	6
1044	3
1045	4
1046	7
1047	2
1048	4
1049	4
1050	5
1051	4
1052	7
1053	3
1054	4
1055	5
1056	4
1057	4
1058	4
1059	4
1060	7
1061	2
1062	2
1063	2
1064	3
1065	3
1066	3
1067	4
1068	6
1069	4
1070	4
1071	7
1072	3
1073	3
1074	4
1075	2
1076	10
1077	3
1078	3
1079	6
1080	5
1081	6
1082	8
1083	4
1084	5
1085	5
1086	2
1087	8
1088	4
1089	4
1090	3
1091	6
1092	5
1093	5
1094	3
1095	3
1096	3
1097	7
1098	4
1099	3
1100	7
1101	4
1102	3
1103	3
1104	2
1105	5
1106	1
1107	3
1108	9
1109	4
1110	4
1111	3
1112	4
1113	4
1114	3
1115	2
1116	5
1117	3
1118	7
1119	5
1120	5
1121	2
1122	5
1123	3
1124	6
1125	4
1126	3
1127	2
1128	4
1129	4
1130	2
1131	2
1132	2
1133	5
1134	3
1135	4
1136	5
1137	4
1138	5
1139	3
1140	6
1141	8
1142	5
1143	3
1144	4
1145	4
1146	5
1147	5
1148	7
1149	4
1150	6
1151	6
1152	3
1153	4
1154	4
1155	4
1156	7
1157	7
1158	8
1159	4
1160	4
1161	5
1162	4
1163	4
1164	6
1165	2
1166	5
1167	3
1168	3
1169	5
1170	5
1171	3
1172	10
1173	6
1174	4
1175	5
1176	3
1177	5
1178	4
1179	3
1180	6
1181	5
1182	4
1183	4
1184	2
1185	3
1186	4
1187	6
1188	7
1189	3
1190	4
1191	4
1192	1
1193	3
1194	3
1195	7
1196	9
1197	3
1198	2
1199	4
1200	3
1201	6
1202	2
1203	5
1204	8
1205	3
1206	4