1	2
2	1
3	1
4	2
5	1
6	1
7	1
8	2
9	2
10	1
11	2
12	1
15	1
16	3
17	3
18	2
19	1
20	1
21	2
22	3
23	1
24	2
25	2
27	2
28	4
29	2
30	2
32	1
33	3
35	2
36	1
38	2
39	2
40	2
41	2
42	1
43	3
44	4
46	2
47	1
48	2
49	1
50	1
51	1
54	2
55	3
56	2
57	3
58	3
59	3
60	2
61	3
65	2
66	2
67	1
68	1
69	1
71	2
72	3
73	1
74	2
76	2
77	5
78	2
79	1
80	2
81	3
82	1
83	1
84	3
85	1
86	3
87	1
88	1
89	2
90	1
91	1
92	2
93	2
94	2
95	3
96	5
98	3
99	4
100	2
101	1
102	2
103	3
104	3
105	1
106	5
107	2
108	1
110	3
112	1
113	1
114	3
115	4
116	6
117	3
118	4
119	2
120	1
121	5
122	1
123	6
124	2
125	2
127	5
128	3
129	3
130	5
131	5
132	2
133	7
134	3
135	3
136	4
137	4
138	2
139	4
140	6
141	7
142	5
145	5
146	3
147	2
148	2
149	2
150	3
151	3
152	3
153	4
154	3
155	4
156	5
157	4
158	3
159	4
160	5
161	3
162	6
163	6
164	7
165	6
166	2
167	5
168	5
169	6
170	11
171	5
172	4
173	2
174	4
175	4
176	4
177	5
178	5
179	3
180	5
181	3
182	6
183	3
184	2
185	1
186	1
187	9
188	2
189	6
190	5
191	2
192	4
193	4
194	5
195	2
196	3
197	2
198	3
199	4
200	3
201	5
202	2
203	9
204	4
205	3
206	4
207	8
208	6
209	2
210	1
211	2
212	5
213	6
214	5
215	8
216	6
217	6
218	4
219	4
220	3
221	3
222	6
223	5
224	4
225	6
226	4
227	3
228	6
229	4
230	4
231	5
232	1
233	4
234	6
235	4
236	5
237	12
238	4
239	6
240	6
241	4
242	5
243	9
244	6
245	4
246	7
247	4
248	2
249	5
250	7
251	4
252	9
253	5
254	6
255	9
256	3
257	5
258	8
259	5
260	10
261	3
262	7
263	7
264	2
265	11
266	6
267	2
268	5
269	8
270	11
271	10
272	2
273	6
274	2
275	6
276	5
277	6
278	7
279	5
280	4
281	9
282	6
283	9
284	1
285	11
286	6
287	10
288	5
289	11
290	2
291	2
292	12
293	8
294	9
295	6
296	9
297	9
298	4
299	6
300	4
301	6
302	6
303	7
304	7
305	7
306	2
307	8
308	10
309	9
310	2
311	6
312	6
313	8
314	8
315	10
316	5
317	7
318	6
319	9
320	7
321	7
322	13
323	8
324	7
325	10
326	7
327	8
328	8
329	8
330	3
331	12
332	6
333	3
334	3
335	12
336	4
337	7
338	7
339	8
340	5
341	9
342	4
343	8
344	8
345	8
346	12
347	6
348	7
349	4
350	5
351	5
352	7
353	11
354	10
355	5
356	8
357	8
358	11
359	11
360	3
361	5
362	3
363	10
364	7
365	4
366	8
367	7
368	9
369	4
370	8
371	9
372	4
373	11
374	5
375	8
376	8
377	4
378	7
379	5
380	7
381	7
382	13
383	7
384	5
385	5
386	3
387	7
388	6
389	4
390	5
391	9
392	5
393	7
394	5
395	8
396	6
397	9
398	4
399	5
400	8
401	9
402	8
403	5
404	7
405	10
406	10
407	8
408	7
409	3
410	3
411	7
412	6
413	8
414	6
415	6
416	6
417	3
418	6
419	3
420	4
421	6
422	6
423	8
424	5
425	11
426	7
427	7
428	4
429	5
430	8
431	3
432	9
433	4
434	6
435	3
436	5
437	4
438	7
439	6
440	5
441	4
442	1
443	4
444	6
445	6
446	3
447	7
448	1
449	9
450	4
451	9
452	7
453	3
454	5
455	6
456	5
457	6
458	5
459	3
460	5
461	4
462	8
463	8
464	4
465	4
466	11
467	7
468	9
469	4
470	3
471	7
472	2
473	7
474	3
475	2
476	8
477	2
478	4
479	5
480	5
481	8
482	6
483	7
484	2
485	1
486	5
487	4
488	6
489	6
490	4
491	2
492	3
493	8
494	6
495	3
496	7
497	11
498	10
499	5
500	4
501	2
502	3
503	6
504	5
505	4
506	3
507	3
508	1
509	1
510	3
511	5
512	4
513	3
514	8
515	4
516	2
517	3
518	4
519	4
520	8
521	6
522	4
523	7
524	4
525	5
526	8
527	2
528	2
529	3
530	6
531	3
532	2
533	1
534	5
535	5
536	4
537	3
538	2
539	5
540	7
541	6
542	3
543	3
544	5
545	8
546	6
547	5
548	1
549	1
550	6
551	1
552	1
553	3
554	1
555	4
556	3
557	1
558	3
559	2
560	7
561	4
562	7
563	2
564	3
565	5
566	5
567	7
568	2
569	6
570	2
571	3
572	5
573	4
574	2
575	4
576	4
577	4
578	5
580	2
581	2
582	1
583	5
584	2
585	1
586	6
587	5
588	7
589	5
590	4
591	2
592	7
593	5
594	2
595	3
596	4
597	3
598	3
599	5
600	5
601	4
602	3
603	3
604	3
605	3
606	3
607	3
608	6
609	6
610	3
611	2
612	4
613	4
614	2
615	3
616	2
617	3
618	6
619	2
620	4
621	2
623	5
624	4
625	4
627	2
629	1
630	4
631	6
632	3
633	1
634	1
635	3
636	5
637	5
638	5
640	6
641	4
642	5
643	2
644	4
645	1
646	5
647	2
648	6
649	5
650	2
651	4
652	6
655	2
656	2
657	4
659	1
660	5
661	3
662	2
663	6
664	2
665	4
666	2
667	7
668	1
669	3
670	3
671	3
672	5
673	1
674	3
675	4
676	5
677	1
678	6
679	3
680	3
681	3
682	3
683	3
684	1
685	3
686	1
687	5
688	3
689	2
690	1
691	1
692	4
694	2
695	2
696	5
697	5
698	1
699	2
700	3
701	4
702	6
703	4
704	3
705	1
706	5
707	4
708	2
709	5
710	2
711	4
712	1
713	4
714	1
715	2
716	2
717	4
718	3
719	2
720	1
721	7
722	2
723	1
724	4
725	7
726	2
727	5
728	2
729	1
730	3
731	8
732	2
733	3
734	4
735	2
736	3
737	1
738	6
739	2
740	2
741	3
742	3
743	2
744	5
745	5
746	2
747	4
748	4
749	5
750	4
751	2
752	2
753	2
755	2
756	1
757	3
759	3
760	3
761	4
762	1
763	4
764	4
765	3
766	1
767	4
768	3
769	3
770	6
771	2
772	1
773	3
774	1
775	1
776	5
777	2
778	3
779	3
780	3
781	6
782	3
783	4
784	1
785	7
786	4
787	2
788	1
789	1
790	2
791	1
792	3
794	1
795	4
796	4
797	5
798	3
800	2
801	2
802	2
803	3
804	1
805	2
806	2
807	4
808	6
809	2
810	4
811	4
812	1
813	2
814	3
815	2
816	5
817	2
818	2
819	1
820	4
821	3
822	2
823	1
824	3
825	3
826	2
827	3
828	6
829	1
830	3
831	2
832	4
833	1
834	2
835	4
836	3
837	1
838	2
839	2
840	4
841	3
842	2
843	1
844	2
845	3
846	1
847	5
848	1
849	5
850	4
851	3
852	3
853	5
854	2
855	4
856	2
857	2
858	2
859	5
860	4
861	3
862	2
863	6
864	5
865	3
866	7
867	1
868	2
869	2
870	4
871	2
872	1
873	3
874	1
875	2
876	3
877	3
878	1
879	2
881	2
882	3
883	1
884	1
885	4
886	2
887	3
888	5
889	4
890	2
891	7
892	2
893	4
895	2
896	3
897	3
898	1
899	2
901	5
902	3
903	1
904	4
906	4
907	4
908	3
909	2
910	2
911	3
912	2
913	3
914	4
915	2
916	3
917	2
918	5
919	4
920	5
921	5
922	3
923	2
924	3
927	3
928	2
929	3
930	2
932	4
933	3
934	2
935	3
936	5
937	1
938	3
939	3
940	4
941	1
943	3
945	2
946	1
947	5
948	4
949	3
951	2
952	1
953	4
954	2
955	2
956	4
957	3
958	1
959	1
960	2
961	5
962	3
963	4
964	2
965	3
967	2
968	1
969	1
970	3
972	2
973	1
974	3
976	1
977	1
978	5
979	3
980	1
981	4
982	2
983	1
984	2
985	1
986	2
987	1
988	3
989	1
990	5
991	2
992	3
993	2
994	3
995	1
996	4
997	3
998	3
1000	2
1001	3
1002	4
1003	1
1004	3
1005	2
1007	4
1008	2
1010	1
1011	5
1012	4
1013	2
1014	3
1015	2
1016	3
1017	4
1018	2
1019	1
1020	1
1021	5
1022	1
1024	2
1025	2
1026	1
1027	2
1028	3
1029	1
1030	3
1031	2
1032	3
1034	3
1035	1
1037	1
1038	3
1041	1
1042	3
1043	1
1044	2
1045	2
1046	1
1047	1
1048	3
1049	3
1050	2
1052	2
1053	4
1054	1
1055	2
1056	1
1058	2
1061	1
1062	1
1063	1
1065	2
1066	2
1067	1
1068	5
1069	1
1070	2
1071	1
1073	1
1075	2
1076	2
1077	1
1079	2
1081	2
1085	2
1086	1
1087	5
1088	2
1089	1
1090	4
1092	2
1094	4
1095	3
1096	1
1097	1
1098	1
1099	3
1100	1
1102	1
1103	1
1104	2
1105	2
1106	1
1107	1
1108	2
1109	1
1110	1
1111	1
1112	3
1113	1
1116	1
1117	2
1118	2
1119	1
1121	2
1122	1
1123	3
1125	3
1127	2
1128	3
1129	1
1130	1
1131	2
1132	1
1133	4
1134	1
1136	2
1137	1
1138	1
1141	2
1142	3
1143	6
1144	2
1145	1
1146	1
1147	1
1149	1
1150	1
1151	1
1152	2
1154	1
1156	2
1157	2
1158	4
1159	5
1160	3
1162	2
1163	1
1164	2
1167	1
1169	4
1171	1
1172	1
1174	1
1175	3
1176	1
1177	2
1178	1
1179	2
1180	1
1181	1
1182	3
1183	4
1184	1
1185	1
1187	2
1188	3
1191	1
1195	2
1197	3
1198	1
1199	2
1200	2
1201	1
1203	2
1204	2
1205	4
1207	5
1210	4
1211	1
1214	2
1215	1
1218	2
1219	2
1220	1
1222	1
1224	1
1225	2
1226	1
1227	2
1229	1
1230	1
1231	5
1232	2
1233	4
1235	1
1236	4
1239	1
1241	3
1244	1
1245	1
1247	4
1248	1
1249	3
1251	2
1252	5
1253	1
1254	1
1256	2
1258	2
1259	2
1260	1
1261	2
1263	2
1264	2
1271	2
1274	1
1275	2
1277	1
1278	1
1279	2
1280	3
1281	1
1283	1
1284	1
1285	2
1287	1
1288	1
1289	1
1290	2
1291	1
1292	1
1293	1
1298	2
1300	2
1301	3
1304	2
1307	1
1308	3
1309	2
1310	2
1311	1
1313	2
1314	1
1315	4
1316	1
1319	2
1320	1
1321	2
1322	1
1323	1
1325	4
1327	2
1328	3
1329	1
1332	3
1334	2
1337	1
1339	1
1341	1
1342	1
1343	3
1344	3
1345	2
1347	1
1348	2
1349	1
1351	4
1353	1
1354	3
1357	3
1358	2
1359	2
1361	1
1363	2
1364	2
1365	1
1366	2
1368	1
1370	1
1372	2
1373	1
1374	2
1375	1
1378	2
1379	1
1383	1
1384	1
1388	1
1389	1
1390	1
1391	1
1393	1
1394	1
1399	1
1400	1
1401	1
1402	1
1404	1
1405	1
1406	1
1407	1
1410	2
1412	4
1413	2
1415	2
1417	1
1418	3
1422	1
1423	2
1424	1
1427	2
1428	1
1429	1
1431	1
1435	1
1436	1
1437	1
1438	1
1441	1
1443	1
1444	1
1445	2
1446	1
1447	1
1448	1
1451	3
1452	1
1455	1
1456	2
1460	1
1464	1
1465	4
1467	1
1468	2
1471	1
1472	1
1474	1
1475	1
1476	3
1477	1
1479	1
1481	1
1482	1
1483	1
1484	1
1485	2
1487	1
1490	2
1491	1
1492	1
1502	1
1503	2
1507	1
1508	1
1509	1
1510	1
1511	1
1513	1
1515	3
1516	1
1517	1
1518	1
1520	2
1523	1
1524	1
1525	2
1528	1
1529	2
1530	1
1533	2
1534	3
1535	2
1536	1
1537	1
1539	1
1544	3
1548	1
1549	1
1550	1
1551	2
1554	1
1555	2
1559	2
1561	1
1564	1
1566	1
1570	1
1571	1
1572	1
1575	1
1577	1
1578	1
1582	1
1585	2
1588	1
1593	2
1594	1
1596	1
1598	1
1601	2
1606	2
1614	3
1615	1
1616	1
1620	1
1622	2
1623	1
1624	2
1628	1
1630	2
1631	1
1632	2
1633	1
1635	1
1639	1
1641	1
1644	1
1646	1
1647	1
1648	1
1649	1
1654	1
1656	1
1658	1
1660	1
1661	1
1662	1
1665	1
1666	1
1667	2
1668	2
1669	1
1671	1
1675	2
1676	1
1678	1
1679	1
1680	1
1681	1
1682	2
1683	1
1684	2
1687	1
1692	1
1694	1
1698	1
1706	1
1708	1
1711	1
1713	1
1714	1
1724	1
1734	1
1741	1
1746	1
1749	1
1753	1
1755	1
1756	1
1759	1
1767	1
1768	1
1775	2
1781	1
1783	2
1784	2
1787	1
1788	1
1789	1
1791	1
1796	1
1797	1
1800	1
1802	1
1806	2
1807	1
1815	3
1816	2
1822	1
1825	1
1826	1
1828	1
1841	1
1842	1
1849	2
1855	1
1862	1
1863	1
1864	1
1866	1
1868	2
1874	1
1876	1
1877	1
1889	1
1891	1
1892	1
1895	1
1896	1
1897	1
1901	1
1905	1
1906	1
1916	1
1920	1
1925	1
1930	1
1934	1
1942	1
1943	1
1951	1
1958	1
1963	1
1969	2
1972	1
1973	2
1977	1
1987	1
1988	2
1992	1
1994	2
1995	1
2000	1
2004	1
2012	1
2024	2
2026	2
2032	2
2044	1
2053	1
2054	1
2062	1
2064	2
2071	1
2073	1
2076	2
2085	2
2094	1
2098	1
2099	1
2103	1
2106	1
2107	1
2109	1
2124	1
2140	1
2142	1
2150	1
2158	1
2159	1
2163	1
2165	1
2169	1
2173	1
2181	1
2186	1
2193	1
2206	1
2213	1
2215	1
2233	1
2238	1
2241	1
2262	1
2264	1
2266	1
2271	1
2273	1
2274	1
2275	1
2279	1
2281	1
2300	1
2305	1
2306	1
2311	1
2330	1
2331	1
2341	2
2345	1
2360	1
2374	1
2375	1
2385	1
2402	1
2403	1
2409	1
2417	1
2423	1
2426	1
2448	1
2477	2
2478	1
2501	1
2503	1
2548	1
2568	1
2571	1
2586	1
2588	1
2592	1
2600	1
2607	1
2615	1
2623	1
2634	1
2638	1
2666	1
2668	1
2684	1
2716	1
2722	1
2726	1
2744	1
2748	1
2769	1
2789	1
2795	1
2812	1
2831	1
2846	1
2853	1
2872	1
2884	1
2901	1
2918	1
2951	1
2960	1
2962	1
2992	1
2993	1
3026	1
3040	1
3062	1
3103	1
3147	1
3173	1
3188	1
3191	1
3198	1
3236	1
3243	1
3247	1
3336	1
3340	1
3352	1
3393	1
3429	1
3437	1
3476	1
3493	1
3505	1
3578	1
3654	1
3692	1
3801	1
3863	1
3899	1
3907	1
3919	1
3979	1
3992	1
4129	1
4323	1
4404	1
4657	1
4668	1
4815	1
4934	1
4944	1
5060	1
5455	1
5598	1
8058	1
8812	1