import java.io.*; import java.util.*; import java.util.stream.*; import static java.lang.Math.*; class FastScanner { // {{{ private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if(ptr < buflen) { return true; } ptr = 0; try { buflen = in.read(buffer); } catch(IOException ex) { ex.printStackTrace(); } if(buflen <= 0) { return false; } return true; } private int readByte() { if(hasNextByte()) { return buffer[ptr++]; } return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) { ++ptr; } } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if(!hasNext()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if(!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if(b == '-') { minus = true; b = readByte(); } if(b < '0' || '9' < b) { throw new NumberFormatException(); } while(true) { if('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if(b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { if(!hasNext()) { throw new NoSuchElementException(); } int n = 0; boolean minus = false; int b = readByte(); if(b == '-') { minus = true; b = readByte(); } if(b < '0' || '9' < b) { throw new NumberFormatException(); } while(true) { if('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if(b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } } // }}} public class Main { private long[] d; private int n; private long x, y; int f(long x, long y) { if(x == 0 && y == 0) { return 0; } long dist = abs(x) + abs(y); if(Arrays.binarySearch(d, dist) >= 0) { return 1; } for(int i=0; i= 0) { return 2; } if(i+1 <= n-1 && Arrays.binarySearch(d, i+1, n-1, aleft) >= 0) { return 2; } } return -1; } private void solve() { FastScanner sc = new FastScanner(); n = sc.nextInt(); d = new long[n]; for(int i=0; i