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