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