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