Problem: Professor Abacus has just built a new computing engine for making numerical tables. It was designed to calculate the values of a polynomial function in one variable at several points at a time. With the polynomial function f(x) = x2 + 2x + 1, for instance, a possible expected calculation result is 1 (= f(0)), 4 (= f(1)), 9 (= f(2)), 16 (= f(3)), and 25 (= f(4)).

It is a pity, however, the engine seemingly has faulty components and exactly one value among those calculated simultaneously is always wrong. With the same polynomial function as above, it can, for instance, output 1, 4, 12, 16, and 25 instead of 1, 4, 9, 16, and 25.

You are requested to help the professor identify the faulty components. As the first step, you should write a program that scans calculation results of the engine and finds the wrong values.



Input

The input is a sequence of datasets, each representing a calculation result in the following format.

d
v0
v1
...
vd+2


Here, d in the first line is a positive integer that represents the degree of the polynomial, namely, the highest exponent of the variable. For instance, the degree of 4x5 + 3x + 0.5 is five and that of 2.4x + 3.8 is one. d is at most five.

The following d + 3 lines contain the calculation result of f(0), f(1), ... , and f(d + 2) in this order, where f is the polynomial function. Each of the lines contains a decimal fraction between -100.0 and 100.0, exclusive.

You can assume that the wrong value, which is exactly one of f(0), f(1), ... , and f(d+2), has an error greater than 1.0. Since rounding errors are inevitable, the other values may also have errors but they are small and never exceed 10-6.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output i in a line when vi is wrong.

Example

Input

2
1.0
4.0
12.0
16.0
25.0
1
-30.5893962764
5.76397083962
39.3853798058
74.3727663177
4
42.4715310246
79.5420238202
28.0282396675
-30.3627807522
-49.8363481393
-25.5101480106
7.58575761381
5
-21.9161699038
-48.469304271
-24.3188578417
-2.35085940324
-9.70239202086
-47.2709510623
-93.5066246072
-82.5073836498
0


Output

2
1
1
6

Solution (in JAVA):

Solution:

import java.io.IOException;
import java.io.PrintWriter;


public class Main {
	int D;
	double[] V = new double[10];
	public void solve() {
		while(true){
			D = nextInt();
			if(D == 0) break;
			for(int i = 0; i < D + 3; i++){
				V[i] = Double.parseDouble(next());
			}
			DoubleMatrix mat = new DoubleMatrix(D + 1, D + 1);
			DoubleVector b = new DoubleVector(D + 1);
			double min = Double.MAX_VALUE;
			int mini = 0;
			for(int i = 0; i < D + 3; i++){
				int idx = 0;
				int j;
				for(j = 0; idx < D + 1; j++){
					if(i == j) continue;
					double po = 1;
					for(int k = 0; k < D + 1; k++){
						mat.set(idx, k, po);
						po *= j;
					}
					b.set(idx, V[j]);
					idx++;
				}
				solve(mat, b);
				if(i == j) j++;
				double po = 1;
				double val = 0;
				for(int k = 0; k < D + 1; k++){
					val += b.get(k) * po;
					po *= j;
				}
				if(Math.abs(val - V[j]) < min){
					min = Math.abs(val - V[j]);
					mini = i;
				}
			}
			out.println(mini);
		}
	}
	public DoubleMatrix identity(int n){
		DoubleMatrix mat = new DoubleMatrix(n, n);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j) mat.set(i, j, 1.0);
				else mat.set(i, j, 0.0);
			}
		}
		return mat;
	}
	
	
	class DoubleMatrix {
		public final int row;
		public final int colum;
		double[] data;
		public DoubleMatrix(int row, int colum){
			this.row = row;
			this.colum = colum;
			this.data = new double[row * colum];
		}
		
		public int index(int r, int c){
			if(0 <= r && r < row && 0 <= c && c <= colum){
				return r * colum + c;
			}else{
				throw new IndexOutOfBoundsException("Matrix size row: " + row + " colum:" + colum + "access: (" + r + "," + c + ")");
			}
		}
		
		public void set(int r, int c, double v){
			this.data[index(r,c)] = v;
		}
		public double get(int r, int c){
			return this.data[index(r,c)];
		}
		
	
		public DoubleMatrix mul(DoubleMatrix mat){
			if(this.colum != mat.row) throw new ArithmeticException();
			DoubleMatrix ans = new DoubleMatrix(this.row, mat.colum);
			for(int i = 0; i < ans.row; i++){
				for(int j = 0; j < ans.colum; j++){
					double sum = 0;
					for(int k = 0; k < this.colum; k++){
						sum += get(i, k) * mat.get(k, j);
					}
					ans.set(i, j, sum);
				}
			}
			return ans;
		}
		
		public DoubleVector mul(DoubleVector vec){
			if(this.colum != vec.size) throw new ArithmeticException();
			DoubleVector ans = new DoubleVector(this.row);
			for(int i = 0; i < ans.size; i++){
				double sum = 0;
				for(int j = 0; j < this.colum; j++){
					sum += get(i, j) * vec.get(j);
				}
				ans.set(i, sum);
			}
			return ans;
		}
		
		public DoubleMatrix pow(int n){
			if(this.colum != this.row) throw new ArithmeticException();
			if(n == 0) return identity(this.row);
			if(n % 2 == 0) return (this.mul(this)).pow(n / 2);
			else return this.mul(this.pow(n - 1));
		}
		
		public String toString(){
			StringBuilder build = new StringBuilder();
			build.append("[");
			for(int i = 0; i < row; i++){
				build.append("[");
				for(int j = 0; j < colum; j++){
					if(j != 0) build.append(",");
					build.append(get(i, j));
				}
				build.append("]");
				if(i != row - 1) build.append(",");
				build.append("\n");
			}
			return build.toString();
		}
	}

	class DoubleVector{
		public final int size;
		private double[] data;
		public DoubleVector(int size){
			this.size = size;
			data = new double[size];
		}

		public void set(int i, double v){
			this.data[i] = v;
		}
		public double get(int i){
			return this.data[i];
		}
		public String toString(){
			StringBuilder build = new StringBuilder();
			build.append("[");
			for(int i = 0; i < size; i++){
					if(i != 0) build.append(",");
					build.append(get(i));
			}
			
			build.append("]");
			return build.toString();
		}
	}
	
	public void solve(DoubleMatrix mat, DoubleVector b){
		int N = mat.row;
		int[] swap = new int[N];
		for(int i = 0; i < N; i++) swap[i] = i;
		
		for(int i = 0; i < N; i++){
			double max = mat.get(swap[i], i);
			int maxi = i;
			for(int j = i + 1; j < N; j++){
				if(max < mat.get(swap[j], i)){
					max = mat.get(swap[j], i);
					maxi = j;
				}
			}
			int tmp = swap[maxi];
			swap[maxi] = swap[i];
			swap[i] = tmp;
			
			double v, val1, val2;
			v = mat.get(swap[i], i);
			for(int j = i + 1; j < N; j++){
				val1 = mat.get(swap[i], j);
				mat.set(swap[i], j, val1 / v);
			}
			b.set(swap[i], b.get(swap[i]) / v);
			mat.set(swap[i], i, 1.0);
			
			for(int j = i + 1; j < N; j++){
				v = mat.get(swap[j], i);
				for(int k = i + 1; k < N; k++){
					val1 = mat.get(swap[j], k);
					val2 = mat.get(swap[i], k);
					mat.set(swap[j], k, val1 - val2 * v);
				}
				val1 = b.get(swap[j]);
				val2 = b.get(swap[i]);
				b.set(swap[j], val1 - val2 * v);
				
				mat.set(swap[j], i, 0.0);
			}
		}
		for(int i = N - 2; i >= 0; i--){
			double val = b.get(swap[i]);
			for(int j = i + 1; j < N; j++){
				val -= mat.get(swap[i], j) * b.get(swap[j]);
			}
			b.set(swap[i], val);
		}
		double[] tmp = new double[N];
		for(int i = 0; i < N; i++){
			tmp[i] = b.get(swap[i]);
		}
		for(int i = 0; i < N; i++){
			b.set(i, tmp[i]);
		}
	}

	private static PrintWriter out;

	public static void main(String[] args) {
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}

	public static int nextInt() {
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(; i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}

	public static long nextLong() {
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(; i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}

	public static String next() {
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}

	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;

	private static int read() {
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return(bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}

	private static boolean isAlNum(int c) {
		return '!' <= c && c <= '~';
	}
}