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