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