1	1
2	1
3	2
4	1
5	3
6	2
7	3
8	1
9	4
10	2
11	3
12	3
13	4
14	2
15	6
16	2
17	4
18	4
19	4
20	2
21	6
22	3
23	5
24	3
25	7
26	3
27	6
28	3
29	3
30	4
31	5
32	2
33	6
34	4
35	7
36	5
37	5
38	4
39	10
40	3
41	5
42	5
43	5
44	4
45	11
46	2
47	4
48	3
49	6
50	6
51	9
52	2
53	4
54	6
55	7
56	5
57	8
58	3
59	7
60	6
61	6
62	4
63	10
64	2
65	10
66	7
67	6
68	4
69	8
70	4
71	6
72	7
73	5
74	2
75	14
76	4
77	9
78	5
79	4
80	4
81	10
82	4
83	6
84	8
85	11
86	4
87	8
88	3
89	4
90	8
91	11
92	4
93	9
94	5
95	10
96	4
97	9
98	8
99	12
100	6
101	6
102	9
103	6
104	6
105	15
106	4
107	6
108	8
109	6
110	9
111	10
112	4
113	5
114	8
115	13
116	6
117	17
118	6
119	12
120	7
121	7
122	5
123	10
124	3
125	14
126	12
127	9
128	2
129	10
130	9
131	7
132	8
133	11
134	4
135	18
136	4
137	5
138	5
139	7
140	8
141	11
142	4
143	12
144	7
145	10
146	3
147	12
148	3
149	6
150	9
151	4
152	7
153	17
154	7
155	13
156	7
157	5
158	4
159	9
160	7
161	15
162	13
163	7
164	5
165	18
166	4
167	5
168	9
169	10
170	10
171	16
172	3
173	5
174	8
175	14
176	6
177	15
178	2
179	6
180	10
181	7
182	6
183	12
184	4
185	13
186	9
187	13
188	7
189	15
190	7
191	7
192	4
193	8
194	3
195	23
196	8
197	7
198	11
199	5
200	6
201	15
202	3
203	9
204	7
205	14
206	7
207	19
208	5
209	13
210	12
211	5
212	3
213	15
214	5
215	14
216	9
217	11
218	5
219	12
220	9
221	12
222	9
223	8
224	4
225	24
226	4
227	8
228	9
229	10
230	5
231	16
232	7
233	7
234	11
235	14
236	3
237	9
238	10
239	4
240	10
241	6
242	8
243	16
244	3
245	15
246	7
247	13
248	7
249	14
250	12
251	9
252	12
253	16
254	7
255	24
256	3
257	6
258	10
259	11
260	8
261	13
262	5
263	8
264	9
265	13
266	8
267	11
268	4
269	11
270	15
271	6
272	6
273	24
274	4
275	18
276	8
277	10
278	5
279	16
280	12
281	7
282	10
283	3
284	6
285	22
286	9
287	14
288	7
289	11
290	8
291	16
292	4
293	11
294	14
295	15
296	3
297	21
298	2
299	17
300	13
301	15
302	6
303	15
304	7
305	18
306	12
307	11
308	9
309	12
310	8
311	7
312	11
313	10
314	8
315	27
316	4
317	8
318	10
319	11
320	5
321	16
322	7
323	11
324	13
325	21
326	6
327	15
328	7
329	14
330	18
331	7
332	3
333	19
334	5
335	12
336	9
337	9
338	8
339	11
340	11
341	16
342	13
343	13
344	7
345	26
346	2
347	11
348	15
349	10
350	10
351	26
352	5
353	5
354	9
355	12
356	7
357	25
358	6
359	9
360	15
361	10
362	7
363	16
364	8
365	13
366	7
367	4
368	7
369	18
370	5
371	11
372	8
373	6
374	10
375	26
376	4
377	12
378	15
379	6
380	9
381	16
382	5
383	10
384	6
385	19
386	4
387	20
388	7
389	8
390	15
391	13
392	8
393	19
394	5
395	11
396	15
397	9
398	3
399	26
400	5
401	8
402	10
403	15
404	3
405	30
406	8
407	15
408	11
409	12
410	10
411	13
412	6
413	14
414	10
415	12
416	6
417	16
418	11
419	11
420	19
421	8
422	3
423	20
424	4
425	21
426	8
427	14
428	5
429	29
430	8
431	8
432	11
433	8
434	11
435	24
436	3
437	14
438	8
439	8
440	10
441	20
442	15
443	6
444	9
445	12
446	5
447	12
448	9
449	11
450	15
451	14
452	6
453	12
454	4
455	25
456	14
457	6
458	4
459	26
460	8
461	10
462	18
463	8
464	6
465	28
466	7
467	7
468	13
469	14
470	9
471	15
472	3
473	16
474	8
475	18
476	7
477	16
478	6
479	13
480	11
481	15
482	6
483	31
484	10
485	21
486	17
487	10
488	4
489	13
490	18
491	12
492	12
493	14
494	13
495	32
496	7
497	17
498	6
499	11
500	11
501	14
502	2
503	8
504	18
505	20
506	10
507	24
508	7
509	11
510	19
511	16
512	4
513	27
514	6
515	15
516	10
517	17
518	7
519	12
520	12
521	9
522	15
523	9
524	7
525	30
526	4
527	16
528	12
529	12
530	10
531	23
532	14
533	14
534	5
535	19
536	5
537	14
538	8
539	20
540	18
541	12
542	5
543	14
544	6
545	15
546	16
547	11
548	5
549	21
550	18
551	13
552	9
553	13
554	7
555	29
556	3
557	7
558	13
559	16
560	12
561	31