0	1
1	1
2	2
3	1
4	3
5	1
6	4
7	1
8	2
9	1
10	1
11	1
12	8
13	1
14	2
15	1
16	1
17	1
18	12
19	1
20	2
21	1
22	1
23	1
24	16
25	1
26	2
27	5
28	1
29	1
30	19
31	1
32	1
33	1
34	1
35	1
36	2
37	1
38	3
39	1
40	1
41	1
42	2
43	1
44	1
45	1
46	1
47	1
48	1
49	1
50	2
51	1
52	2
53	1
54	1
55	1
56	1
57	1
58	1
59	1
60	2
61	1
62	2
63	2
64	2
65	1
66	1
67	1
68	1
69	6
70	1
71	1
72	2
73	1
74	1
75	1
76	8
77	11
78	8
79	1
80	2
81	1
82	12
83	1
84	1
85	1
86	9
87	1
88	2
89	1
90	2
91	1
92	1
93	1
94	1
95	3
96	1
97	1
98	1
99	13
100	2
101	1
102	4
103	1
104	2
105	1
106	2
107	1
108	1
109	1
110	1
111	2
112	2
113	1
114	26
115	2
116	1
117	1
118	1
119	7
120	2
121	4
122	1
123	4
124	8
125	1
126	4
127	1
128	2
129	2
130	8
131	1
132	2
133	1
134	4
135	1
136	1
137	1
138	1
139	1
140	1
141	2
142	2
143	2
144	2
145	1
146	1
147	1
148	1
149	1
150	2
151	1
152	1
153	1
154	8
155	1
156	2
157	1
158	4
159	2
160	1
161	2
162	5
163	1
164	1
165	1
166	1
167	1
168	2
169	1
170	6
171	1
172	1
173	1
174	1
175	1
176	2
177	1
178	2
179	1
180	1
181	1
182	1
183	5
184	1
185	1
186	1
187	1
188	1
189	1
190	3
191	1
192	2
193	1
194	2
195	1
196	68
197	1
198	12
199	1
200	2
201	1
202	2
203	1
204	2
205	2
206	1
207	1
208	2
209	1
210	5
211	1
212	2
213	1
214	3
215	1
216	1
217	9
218	1
219	1
220	2
221	2
222	2
223	1
224	1
225	1
226	4
227	1
228	1
229	1
230	1
231	1
232	1
233	1
234	5
235	1
236	1
237	9
238	2
239	1
240	1
241	1
242	1
243	1
244	4
245	1
246	33
247	2
248	6
249	1
250	2
251	1
252	2
253	1
254	3
255	1
256	1
257	1
258	3
259	1
260	1
261	1
262	1
263	1
264	7
265	1
266	2
267	2
268	1
269	1
270	1
271	1
272	1
273	2
274	2
275	1
276	8
277	1
278	2
279	1
280	10
281	1
282	1
283	1
284	2
285	3
286	18
287	1
288	2
289	2
290	1
291	1
292	12
293	1
294	1
295	1
296	9
297	5
298	1
299	1
300	4
301	1
302	4
303	1
304	2
305	1
306	1
307	1
308	2
309	1
310	1
311	1
312	1
313	1
314	13
315	19
316	1
317	1
318	106
319	1
320	2
321	1
322	3
323	16
324	2
325	5
326	1
327	1
328	3
329	1
330	6
331	1
332	2
333	1
334	1
335	1
336	2
337	1
338	2
339	1
340	2
341	1
342	1
343	1
344	2
345	1
346	1
347	1
348	10
349	1
350	1
351	2
352	1
353	1
354	2
355	2
356	1
357	1
358	1
359	1
360	1
361	1
362	1
363	2
364	2
365	1
366	22
367	1
368	2
369	3
370	84
371	1
372	2
373	1
374	7
375	5
376	1
377	2
378	1
379	1
380	2
381	1
382	1
383	1
384	1
385	1
386	1
387	1
388	1
389	1
390	1
391	10
392	1
393	1
394	2
395	4
396	1
397	1
398	2
399	1
400	3
401	1
402	2
403	5
404	4
405	2
406	1
407	1
408	1
409	1
410	1
411	6
412	1
413	1
414	2
415	1
416	2
417	1
418	1
419	1
420	14
421	421
422	8
423	1
424	1
425	1
426	2
427	2
428	1
429	2
430	1
431	1
432	1
433	1
434	1
435	1
436	2
437	1
438	2
439	1
440	1
441	1
442	4
443	1
444	2
445	1
446	8
447	1
448	2
449	1
450	4
451	2
452	2
453	1
454	1
455	15
456	1
457	1
458	1
459	1
460	1
461	1
462	43
463	1
464	1
465	1
466	1
467	1
468	1
469	1
470	1
471	2
472	4
473	7
474	1
475	4
476	10
477	3
478	1
479	1
480	1
481	2
482	2
483	1
484	1
485	3
486	1
487	1
488	1
489	2
490	6
491	1
492	1
493	6
494	2
495	3
496	1
497	1
498	8
499	1
500	10
501	1
502	1
503	1
504	8
505	1
506	2
507	1
508	5
509	1
510	2
511	1
512	2
513	1
514	1
515	1
516	1
517	2
518	2
519	1
520	2
521	1
522	1
523	1
524	2
525	3
526	1
527	2
528	1
529	23
530	1
531	1
532	2
533	10
534	2
535	7
536	1
537	2
538	2
539	1
540	1
541	1
542	1
543	2
544	2
545	1
546	10
547	1
548	2
549	2
550	1
551	1
552	1
553	2
554	1
555	1
556	1
557	1
558	1
559	5
560	2
561	1
562	6
563	1
564	1
565	2
566	2
567	1
568	3
569	1
570	1
571	1
572	1
573	1
574	2
575	3
576	4
577	1
578	1
579	1
580	1
581	1
582	1
583	1
584	1
585	1
586	1
587	1
588	2
589	1
590	4
591	1
592	7
593	1
594	78
595	1
596	4
597	2
598	1
599	1
600	1
601	1
602	1
603	1
604	2
605	1
606	1
607	1
608	1
609	1
610	5
611	1
612	1
613	1
614	1
615	1
616	1
617	1
618	1
619	1
620	2
621	1
622	2
623	3
624	2
625	1
626	2
627	1
628	1
629	4
630	1
631	1
632	2
633	1
634	1
635	3
636	1
637	1
638	3
639	3
640	2
641	1
642	2
643	1
644	2
645	6
646	1
647	1
648	1
649	38
650	1
651	3
652	2
653	1
654	2
655	1
656	2
657	1
658	1
659	1
660	1
661	1
662	3
663	1
664	1
665	1
666	1
667	1
668	1
669	1
670	2
671	1
672	2
673	1
674	1
675	2
676	2
677	1
678	1
679	1
680	2
681	1
682	2
683	1
684	1
685	1
686	1
687	1
688	2
689	1
690	1
691	1
692	4
693	1
694	1
695	25
696	1
697	24
698	4
699	2
700	2
701	1
702	1
703	2
704	2
705	1
706	1
707	1
708	1
709	1
710	1
711	2
712	4
713	1
714	1
715	3
716	1
717	1
718	5
719	1
720	2
721	1
722	2
723	1
724	1
725	1
726	1
727	1
728	1
729	1
730	4
731	3
732	2
733	1
734	1
735	2
736	1
737	1
738	2
739	1
740	2
741	1
742	4
743	1
744	1
745	1
746	1
747	2
748	2
749	3
750	10
751	1
752	6
753	1
754	1
755	1
756	6
757	1
758	266
759	1
760	12
761	1
762	3
763	1
764	8
765	2
766	8
767	1
768	1
769	1
770	4
771	1
772	20
773	1
774	2
775	1
776	2
777	5
778	3
779	1
780	1
781	2
782	1
783	2
784	1
785	4
786	1
787	1
788	2
789	1
790	1
791	2
792	12
793	1
794	1
795	2
796	2
797	1
798	2
799	1
800	4
801	1
802	1
803	20
804	1
805	1
806	2
807	1
808	1
809	1
810	1
811	1
812	1
813	1
814	1
815	1
816	2
817	28
818	1
819	1
820	1
821	1
822	2
823	1
824	2
825	1
826	1
827	1
828	1
829	1
830	1
831	1
832	1
833	2
834	1
835	1
836	4
837	1
838	13
839	1
840	1
841	1
842	2
843	1
844	2
845	1
846	2
847	1
848	2
849	1
850	1
851	1
852	2
853	1
854	2
855	110
856	2
857	1
858	6
859	1
860	1
861	1
862	2
863	1
864	2
865	1
866	2
867	1
868	1
869	1
870	1
871	1
872	1
873	3
874	6
875	1
876	2
877	1
878	1
879	4
880	18
881	1
882	1
883	1
884	4
885	1
886	4
887	1
888	1
889	3
890	1
891	1
892	3
893	1
894	1
895	2
896	2
897	10
898	8
899	1
900	2
901	1
902	2
903	1
904	1
905	1
906	1
907	1
908	1
909	11
910	4
911	1
912	2
913	1
914	1
915	1
916	1
917	1
918	1
919	1
920	2
921	1
922	6
923	3
924	4
925	1
926	4
927	1
928	1
929	1
930	1
931	6
932	4
933	1
934	11
935	1
936	3
937	1
938	1
939	1
940	1
941	1
942	1
943	3
944	1
945	2
946	1
947	1
948	27
949	2
950	1
951	1
952	1
953	1
954	1
955	3
956	1
957	1
958	1
959	1
960	1
961	1
962	2
963	2
964	1
965	1
966	1
967	1
968	3
969	2
970	2
971	1
972	13
973	1
974	1
975	97
976	1
977	1
978	1
979	7
980	6
981	5
982	2
983	1
984	1
985	1
986	1
987	1
988	1
989	3
990	1
991	1
992	1
993	3
994	2
995	2
996	5
997	1
998	1
999	2
1000	2
1001	3
1002	2
1003	3
1004	2
1005	17
1006	1
1007	6
1008	1
1009	1
1010	4
1011	1
1012	2
1013	1
1014	132
1015	1
1016	1
1017	10
1018	6
1019	1
1020	1
1021	1
1022	2
1023	20
1024	3
1025	3
1026	1
1027	1
1028	103
1029	3
1030	2
1031	1
1032	12
1033	1
1034	1
1035	3
1036	2
1037	69
1038	3
1039	1
1040	12
1041	1
1042	1
1043	1
1044	1
1045	1
1046	3
1047	1
1048	1
1049	1
1050	4
1051	1
1052	4
1053	1
1054	4
1055	3
1056	1
1057	2
1058	1
1059	1
1060	1
1061	1
1062	1
1063	1
1064	4
1065	2
1066	1
1067	3
1068	2
1069	1
1070	2
1071	1
1072	3
1073	1
1074	1
1075	1
1076	1
1077	7
1078	3
1079	1
1080	5
1081	1
1082	1
1083	1
1084	1
1085	1
1086	4
1087	1
1088	1
1089	1
1090	1
1091	1
1092	1
1093	1
1094	2
1095	1
1096	1
1097	1
1098	2
1099	1
1100	1
1101	2
1102	7
1103	1
1104	1
1105	2
1106	1
1107	2
1108	1
1109	1
1110	2
1111	3
1112	2
1113	1
1114	1
1115	1
1116	1
1117	1
1118	2
1119	1
1120	2
1121	1
1122	3
1123	1
1124	3
1125	9
1126	1
1127	1
1128	2
1129	1
1130	1
1131	1
1132	2
1133	1
1134	1
1135	1
1136	7
1137	1
1138	1
1139	1
1140	22
1141	1
1142	2
1143	1
1144	1
1145	1
1146	2
1147	1
1148	4
1149	1
1150	2
1151	1
1152	1
1153	1
1154	2
1155	2
1156	1
1157	1
1158	1
1159	15
1160	2
1161	1
1162	3
1163	1
1164	1
1165	3
1166	1
1167	1
1168	1
1169	1
1170	1
1171	1
1172	1
1173	4
1174	2
1175	1
1176	1
1177	1
1178	1
1179	1
1180	1
1181	1
1182	1
1183	1
1184	1
1185	1
1186	5
1187	1
1188	2
1189	1
1190	6
1191	2
1192	2
1193	1
1194	1
1195	1
1196	1
1197	2
1198	2
1199	1
1200	8
1201	1
1202	14
1203	2
1204	1
1205	2
1206	1
1207	1
1208	1
1209	1
1210	2
1211	1
1212	2
1213	1
1214	7
1215	19
1216	4
1217	1
1218	1
1219	1
1220	1
1221	4
1222	1
1223	1
1224	2
1225	1
1226	2
1227	2
1228	2
1229	1
1230	2
1231	1
1232	1
1233	1
1234	2
1235	1
1236	2
1237	1
1238	2
1239	1
1240	2
1241	7
1242	1
1243	65
1244	8
1245	2
1246	4
1247	1
1248	10
1249	1
1250	20
1251	2
1252	18
1253	4
1254	6
1255	1
1256	1
1257	2
1258	1
1259	1
1260	2
1261	1
1262	1
1263	1
1264	1
1265	6
1266	2
1267	2
1268	2
1269	1
1270	1
1271	1
1272	1
1273	1
1274	2
1275	1
1276	2
1277	1
1278	3
1279	1
1280	1
1281	1
1282	1
1283	1
1284	2
1285	1
1286	2
1287	1
1288	1
1289	1
1290	1
1291	1
1292	5
1293	1
1294	1
1295	1
1296	2
1297	1
1298	2
1299	1
1300	6
1301	1
1302	1
1303	1
1304	6
1305	1
1306	1
1307	1
1308	2
1309	2
1310	2
1311	2
1312	3
1313	1
1314	1
1315	1
1316	1
1317	1
1318	1
1319	1
1320	1
1321	1
1322	1
1323	1
1324	1
1325	5
1326	3
1327	1
1328	1
1329	1
1330	20
1331	7
1332	1
1333	12
1334	1
1335	1
1336	1
1337	1
1338	4
1339	1
1340	2
1341	3
1342	1
1343	3
1344	1
1345	2
1346	2
1347	1
1348	3
1349	3
1350	2
1351	1
1352	1
1353	1
1354	4
1355	2
1356	1
1357	1
1358	2
1359	1
1360	2
1361	1
1362	1
1363	1
1364	2
1365	4
1366	2
1367	1
1368	1
1369	1
1370	1
1371	1
1372	2
1373	1
1374	1
1375	1
1376	1
1377	1
1378	1
1379	1
1380	2
1381	1
1382	1
1383	1271
1384	1
1385	12
1386	1
1387	2
1388	1
1389	1
1390	1
1391	1
1392	2
1393	5
1394	2
1395	17
1396	1
1397	3
1398	1
1399	1
1400	1
1401	13
1402	1
1403	1
1404	1
1405	1
1406	2
1407	4
1408	1
1409	1
1410	2
1411	1
1412	2
1413	1
1414	2
1415	1
1416	2
1417	1
1418	1
1419	2
1420	1
1421	1
1422	2
1423	1
1424	15
1425	1
1426	2
1427	1
1428	54
1429	1
1430	2
1431	2
1432	1
1433	1
1434	2
1435	1
1436	46
1437	1
1438	1
1439	1
1440	1
1441	1
1442	1
1443	1
1444	4
1445	1
1446	1
1447	1
1448	2
1449	9
1450	1
1451	1
1452	2
1453	1
1454	2
1455	1
1456	504
1457	4
1458	1
1459	1
1460	1
1461	1
1462	4
1463	1
1464	2
1465	2
1466	2
1467	1
1468	1
1469	1
1470	1
1471	1
1472	1
1473	1
1474	5
1475	1
1476	4
1477	2
1478	1
1479	2
1480	1
1481	1
1482	1
1483	1
1484	1
1485	1
1486	2
1487	1
1488	4
1489	1
1490	33
1491	1
1492	2
1493	1
1494	2
1495	1
1496	1
1497	2
1498	2
1499	1
1500	1
1501	88
1502	7
1503	1
1504	1
1505	6
1506	1
1507	1
1508	528
1509	1
1510	2
1511	1
1512	1
1513	1
1514	2
1515	1
1516	1
1517	1
1518	4
1519	2
1520	1
1521	1
1522	1
1523	1
1524	12
1525	1
1526	20
1527	1
1528	1
1529	1
1530	2
1531	1
1532	2
1533	1
1534	1
1535	1
1536	4
1537	3
1538	2
1539	17
1540	1
1541	2
1542	2
1543	1
1544	1
1545	1
1546	1
1547	3
1548	1
1549	1
1550	1
1551	4
1552	1
1553	1
1554	1
1555	2
1556	3
1557	4
1558	2
1559	1
1560	4
1561	1
1562	1
1563	1
1564	1
1565	2
1566	1
1567	1
1568	1
1569	4
1570	3
1571	1
1572	1
1573	2
1574	41
1575	1
1576	1
1577	3
1578	1
1579	1
1580	2
1581	1
1582	2
1583	1
1584	2
1585	2
1586	1
1587	1
1588	1
1589	1
1590	1
1591	1
1592	1
1593	2
1594	2
1595	44
1596	1
1597	1
1598	1
1599	1
1600	1
1601	1
1602	2
1603	1
1604	1
1605	4
1606	9
1607	1
1608	1
1609	1
1610	1
1611	1
1612	1
1613	1
1614	1
1615	1
1616	6
1617	2
1618	6
1619	1
1620	2
1621	1
1622	2
1623	1
1624	1
1625	1
1626	2
1627	1
1628	7
1629	1
1630	1
1631	2
1632	1
1633	2
1634	6
1635	1
1636	1
1637	1
1638	1
1639	1
1640	2
1641	2
1642	3
1643	1
1644	1
1645	1
1646	1
1647	3
1648	2
1649	1
1650	6
1651	1
1652	14
1653	1
1654	4
1655	1
1656	1
1657	1
1658	1
1659	1
1660	2
1661	1
1662	35
1663	1
1664	2
1665	4
1666	1
1667	1
1668	9
1669	1
1670	2
1671	12
1672	2
1673	66
1674	1
1675	1
1676	2
1677	1