The 7 puzzle consists of 8 square cards and a frame that fits them snugly. Each card is numbered 0, 1, 2, ..., 7 to distinguish them from each other. You can arrange two cards vertically and four cards horizontally in the frame.

7 When you start the puzzle, first put all the cards in the frame. Only 0 cards in the frame can be swapped with adjacent cards on the top, bottom, left, and right. For example, when the frame state is shown in Figure (a), if you exchange the position with the 7 card adjacent to the right of the 0 card, you will get the state shown in Figure (b). Alternatively, the state shown in Fig. (A) can be changed to the state shown in Fig. (C) by exchanging the position with the adjacent 2 card under the 0 card. In the state shown in Fig. (A), the cards with 0 and the cards adjacent to the top, bottom, left, and right are only the cards 7 and 2, so other positions cannot be swapped.

The purpose of the game is to arrange the cards neatly so that they are in the state shown in Figure (d). Create a program that takes the initial state as input and outputs the minimum number of steps required to align the cards neatly. However, it is possible to move from the state of the entered card to the state shown in Fig. (D).

The input data is given eight numbers per line, separated by blanks. These represent the initial sequence of cards. For example, the number representation in Figure (a) is 0 7 3 4 2 5 1 6 and Figure (c) is 2 7 3 4 0 5 1 6.

<image> | <image>
--- | ---
Figure (a) 0 7 3 4 2 5 1 6 | Figure (b) 7 0 3 4 2 5 1 6


<image> | <image>
--- | ---
Figure (c) 2 7 3 4 0 5 1 6 | Figure (d) 0 1 2 3 4 5 6 7 (final state)




Input

Multiple puzzles are given in the above format. Please process until the end of the input. No more than 1,000 puzzles will be given.

Output

For each puzzle, output the minimum number of steps to move to the final state on one line.

Example

Input

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


Output

0
1
28
import java.io.*;
import java.math.BigInteger;
import java.util.*;

class Puzzle extends MyUtil{
	public String str;
	public int zero;
	public int[] arr;
	
	Puzzle(String str){
		this.str = str;
		arr = parseInt(str.split(" "));
		for(int i = 0; i < 8; i++){
			if(arr[i] == 0) zero = i;
		}
	}
	
	Puzzle(int[] arr){
		this.arr = arr;
		str = "" + arr[0];
		if(arr[0] == 0) zero = 0;
		for(int i = 1; i < 8; i++){
			str += " " + arr[i];
			if(arr[i] == 0) zero = i;
		}
	}
	
	public void p(){
		p(str);
		p("zero: " + zero);
	}
	
	public Puzzle swap(int swap_count){
		int[] nextArr = cp(arr);
		nextArr[zero] = nextArr[zero + swap_count];
		nextArr[zero + swap_count] = 0;
		Puzzle p = new Puzzle(nextArr);
		return p;
	}
	
	public Puzzle right(){
		if(zero == 3 || zero == 7) return null;
		return swap(1);
	}
	
	public Puzzle left(){
		if(zero == 0 || zero == 4) return null;
		return swap(-1);
	}
	
	public Puzzle ud(){
		if(zero <= 3) return swap(4);
		return swap(-4);
	}
}

/**
 * @author yoshikyoto
 */
class Main extends MyUtil{
	public static ArrayList<ArrayList<Integer>> g;
	
	public static HMSI map = new HMSI();
	
	public static void main(String args[]) throws Exception{
		// 最初にBFSでmapを作っておく
		QS q = new QS();
		String g = "0 1 2 3 4 5 6 7";
		map.add(g, 0);
		q.add(g);
		
		while(q.size() > 0){
			String str = q.pop();
			int count = map.get(str);
			Puzzle curr = new Puzzle(str);
	
			Puzzle next = curr.right();
			if(next != null && !map.containsKey(next.str)){
				q.add(next.str);
				map.add(next.str, count + 1);
			}
			
			next = curr.left();
			if(next != null && !map.containsKey(next.str)){
				q.add(next.str);
				map.add(next.str, count + 1);
			}
			
			next = curr.ud();
			if(!map.containsKey(next.str)){
				q.add(next.str);
				map.add(next.str, count + 1);
			}
		}
		
		String line;
		while((line = readLine()) != null){
			p(map.get(line));
		}
	}
}

/**
 * 整数を数え上げたりするクラス
 * new Prime(int n) でnまでエラトステネスの篩を実行。
 * @author yoshikyoto
 * @param a[i] iが素数の時true
 * @param count[i] i以下の素数の数
 */
class Prime{
	boolean[] a;
	int[] count;
	Prime(int n){
		a = new boolean[n+1];
		a[0] = false; a[1] = false;
		for(int i = 2; i <= n; i++) a[i] = true;
		// ふるい
		for(int i = 2; i < (n - 3) / 2; i++)
			if(a[i]) for(int j = 2; j * i <= n; j++)
					a[j * i] = false;
		
		// 数え上げ
		count = new int[n+1];
		count[0] = 0;
		for(int i = 1; i <= n; i++){
			int gain = 0;
			if(a[i]) gain = 1;
			count[i] = count[i-1] + gain;
		}
	}
}

class AI extends ArrayList<Integer>{}
class SI extends Stack<Integer>{}

class HMI<E> extends HashMap<E, Integer>{
	ArrayList<E> keyArray = new ArrayList<E>();
	public void add(E key){add(key, 1);}
	public void add(E key, Integer value){
		if(containsKey(key)){value += get(key);
		}else{keyArray.add(key);}
		put(key, value);
	}
}

class HMSI extends HMI<String>{}
class Q<E> extends ArrayDeque<E>{
	public void push(E item){add(item);}
	public E pop(){return poll();}
}
class QS extends Q<String>{}
class QI extends Q<Integer>{}

class MyUtil extends MyIO{
	public static long start_time = 0;
	public static void start(){start_time = System.currentTimeMillis();}
	public static void end(){
		if(start_time == 0) return;
		long time = System.currentTimeMillis() - start_time;
		if(DEBUG) p(time + "ms");
	}
	public static int digit(int n){return String.valueOf(n).length();}
	public static String reverse(String s){
		StringBuffer sb = new StringBuffer(s);
		return sb.reverse().toString();
	}
	public static void sort(int[] a){Arrays.sort(a);}
	public static void dsort(int[] a){
		Arrays.sort(a);
		int l = a.length;
		for(int i = 0; i < l/2; i++){
			int tmp = a[i]; a[i] = a[l-1-i]; a[l-1-i] = tmp;
		}
	}
	public static void sleep(int t){try{Thread.sleep(t);}catch(Exception e){}}
	public static int sum(int[] a){int s = 0; for(int i = 0; i < a.length; i++)s+=a[i]; return s;}
	public static int[] cp(int[] a){
		int[] b = new int[a.length];
		for(int i = 0; i < a.length; i++) b[i] = a[i];
		return b;
	}
}

class MyIO extends MyMath{
	static Scanner sc = new Scanner(new InputStreamReader(System.in));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static boolean DEBUG = false;
	public static int[] readIntMap() throws IOException{return parseInt(readLine().split(" "));}
	public static String readLine() throws IOException{return br.readLine();}
	public static int readInt() throws IOException{return Integer.parseInt(br.readLine());}
	public static void p(Object o){System.out.println(o.toString());}
	public static void pr(Object o){System.out.print(o.toString());}
	public static void d(Object o){if(DEBUG)System.out.println(o.toString());}
	public static void dr(Object o){if(DEBUG)System.out.print(o.toString());}
	public static void da(Object[] o){if(DEBUG)System.out.println(Arrays.toString(o));}
	public static void da(int[] arr){if(DEBUG)System.out.println(Arrays.toString(arr));}
	public static void da(double[] arr){if(DEBUG)System.out.println(Arrays.toString(arr));}
	public static void da(boolean[] arr){if(DEBUG)System.out.println(Arrays.toString(arr));}
	public static int[] parseInt(String[] arr){
		int[] res = new int[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Integer.parseInt(arr[i]);
		return res;
	}
	public static double[] parseDouble(String[] arr){
		double[] res = new double[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Double.parseDouble(arr[i]);
		return res;
	}
	public static boolean[] parseBool(String[] arr){
		int[] t = parseInt(arr);
		boolean[] res = new boolean[t.length];
		for(int i = 0; i < t.length; i++){
			if(t[i] == 1){res[i] = true;
			}else{res[i] = false;}
		}
		return res;
	}
	public static int parseInt(Object o){return Integer.parseInt(o.toString());}
}

class MyMath{
	/**
	 * 弧度法の角度を入力してsinの値を返す（Math.sin の入力はラジアン）
	 */
	public static double sin(int r){return Math.sin(Math.toRadians(r));}

	/**
	 * 弧度法の角度を入力してcosの値を返す（Math.sin の入力はラジアン）
	 */
	public static double cos(int r){return Math.cos(Math.toRadians(r));}
	public static int max(int a, int b){return Math.max(a, b);}
	public static int min(int a, int b){return Math.min(a, b);}
	public static boolean isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
	    // 並行な場合
	    int m = (x2-x1)*(y4-y3)-(y2-y1)*(x4-x3);
	    if(m == 0) return false;
	    // 媒介変数の値が0より大きく1以下なら交差する、これは問題の状況によって変わるかも。
	    double r =(double)((y4-y3)*(x3-x1)-(x4-x3)*(y3-y1))/m;
	    double s =(double)((y2-y1)*(x3-x1)-(x2-x1)*(y3-y1))/m;
	    return (0 < r && r <= 1 && 0 < s && s <= 1);
	}
	public static boolean isParallel(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
	    if((x2-x1)*(y4-y3) == (y2-y1)*(x4-x3)) return true;
	    else return false;
	}
	public static double sq(double d){return d*d;}
	public static int sq(int i){return i*i;}
	public static int sqdist(int x1, int y1, int x2, int y2){
		return sq(x1-x2) + sq(y1-y2);}
	public static double sqdist(double x1, double y1, double x2, double y2){
		return sq(x1-x2) + sq(y1-y2);}
	public static double dist(int x1, int y1, int x2, int y2){
		return Math.sqrt(sqdist(x1, y1, x2, y2));}
	public static double dist(double x1, double y1, double x2, double y2){
		return Math.sqrt(sqdist(x1, y1, x2, y2));}
}