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