Problem: Pink Floyd are pulling a prank on Roger Waters. They know he doesn't like [walls](https://www.youtube.com/watch?v=YR5ApYxkU-U), he wants to be able to walk freely, so they are blocking him from exiting his room which can be seen as a grid.

Roger Waters has a square grid of size n× n and he wants to traverse his grid from the upper left (1,1) corner to the lower right corner (n,n). Waters can move from a square to any other square adjacent by a side, as long as he is still in the grid. Also except for the cells (1,1) and (n,n) every cell has a value 0 or 1 in it.

Before starting his traversal he will pick either a 0 or a 1 and will be able to only go to cells values in which are equal to the digit he chose. The starting and finishing cells (1,1) and (n,n) are exempt from this rule, he may go through them regardless of picked digit. Because of this the cell (1,1) takes value the letter 'S' and the cell (n,n) takes value the letter 'F'.

For example, in the first example test case, he can go from (1, 1) to (n, n) by using the zeroes on this path: (1, 1), (2, 1), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)

The rest of the band (Pink Floyd) wants Waters to not be able to do his traversal, so while he is not looking they will invert at most two cells in the grid (from 0 to 1 or vice versa). They are afraid they will not be quick enough and asked for your help in choosing the cells.  Note that you cannot invert cells (1, 1) and (n, n).

We can show that there always exists a solution for the given constraints.

Also note that Waters will pick his digit of the traversal after the band has changed his grid, so he must not be able to reach (n,n) no matter what digit he picks.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 50). Description of the test cases follows.

The first line of each test case contains one integers n (3 ≤ n ≤ 200).

The following n lines of each test case contain the binary grid, square (1, 1) being colored in 'S' and square (n, n) being colored in 'F'.

The sum of values of n doesn't exceed 200.

Output

For each test case output on the first line an integer c (0 ≤ c ≤ 2) — the number of inverted cells.

In i-th of the following c lines, print the coordinates of the i-th cell you inverted. You may not invert the same cell twice.  Note that you cannot invert cells (1, 1) and (n, n).

Example

Input


3
4
S010
0001
1000
111F
3
S10
101
01F
5
S0101
00000
01111
11111
0001F


Output


1
3 4
2
1 2
2 1
0

Note

For the first test case, after inverting the cell, we get the following grid:
    
    
      
    S010  
    0001  
    1001  
    111F  
    

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
public class Solution{
static FastScanner sc;
static PrintWriter pw;
static void pn(Object o){pw.println(o);}
static void p(Object o){pw.print(o);}
static Random rand = new Random();
// references
    // IBIG = 1e9 + 7
    // IMAX ~= 2e9
    // LMAX ~= 9e18
 
    // constants
    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    // math util
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int minof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
    static long minof(long a, long b, long c) {return min(a, min(b, c));}
    static long minof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
    static int maxof(int a, int b, int c) {return max(a, max(b, c));}
    static int maxof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
    static long maxof(long a, long b, long c) {return max(a, max(b, c));}
    static long maxof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
    static int powi(int a, int b) {if (a == 0) return 0; int ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if (a == 0) return 0; long ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int fli(double d) {return (int) d;}
    static int cei(double d) {return (int) Math.ceil(d);}
    static long fll(double d) {return (long) d;}
    static long cel(double d) {return (long) Math.ceil(d);}
    static int gcf(int a, int b) {return b == 0 ? a : gcf(b, a % b);}
    static long gcf(long a, long b) {return b == 0 ? a : gcf(b, a % b);}
    static int lcm(int a, int b) {return a * b / gcf(a, b);}
    static long lcm(long a, long b) {return a * b / gcf(a, b);}
    static int randInt(int min, int max) {return rand.nextInt(max - min + 1) + min;}
    static long mix(long x) {x += 0x9e3779b97f4a7c15L; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L; x = (x ^ (x >> 27)) * 0x94d049bb133111ebL; return x ^ (x >> 31);}
    // array util
    static void reverse(int[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(int [] a, int n, int k)
    {
        if (k > n)
        {
            System.out.println( "Invalid k");
            return;
        }
     
        // One by one reverse first
        // and last elements of a[0..k-1]
        for (int i = 0; i < k / 2; i++)
        {
            int tempswap = a[i];
                a[i] = a[k - i - 1];
                a[k - i - 1] = tempswap;            
        }
    }
    static void reverse(long[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(double[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {double swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(char[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void shuffle(int[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(double[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); Arrays.parallelSort(a);}
    static void rsort(long[] a) {shuffle(a); Arrays.parallelSort(a);}
    static void rsort(double[] a) {shuffle(a); Arrays.parallelSort(a);}
    static int[] copy(int[] a) {int[] ans = new int[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static long[] copy(long[] a) {long[] ans = new long[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static double[] copy(double[] a) {double[] ans = new double[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static char[] copy(char[] a) {char[] ans = new char[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    // graph util
    static List<List<Integer>> g(int n) {List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; ++i) g.add(new ArrayList<>()); return g;}
    static List<Set<Integer>> sg(int n) {List<Set<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; ++i) g.add(new HashSet<>()); return g;}
    static void c(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v); g.get(v).add(u);}
    static void cto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v);}
    static void dc(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v); g.get(v).remove(u);}
    static void dcto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v);}
    // input
    // static void r() throws IOException {input = new StringTokenizer(rline());}
    // static int ri() throws IOException {return Integer.parseInt(rline());}
    // static long rl() throws IOException {return Long.parseLong(rline());}
    // static double rd() throws IOException {return Double.parseDouble(rline());}
    // static int[] ria(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni(); return a;}
    // static int[] riam1(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni() - 1; return a;}
    // static long[] rla(int n) throws IOException {long[] a = new long[n]; r(); for (int i = 0; i < n; ++i) a[i] = nl(); return a;}
    // static double[] rda(int n) throws IOException {double[] a = new double[n]; r(); for (int i = 0; i < n; ++i) a[i] = nd(); return a;}
    // static char[] rcha() throws IOException {return rline().toCharArray();}
    // static String rline() throws IOException {return br.readLine();}
    // static String n() {return input.nextToken();}
    // static int rni() throws IOException {r(); return ni();}
    // static int ni() {return Integer.parseInt(n());}
    // static long rnl() throws IOException {r(); return nl();}
    // static long nl() {return Long.parseLong(n());}
    // static double rnd() throws IOException {r(); return nd();}
    // // static double nd() {return Double.parseDouble(n());}
    // static List<List<Integer>> rg(int n, int m) throws IOException {List<List<Integer>> g = g(n); for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1); return g;}
    // static void rg(List<List<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1);}
    // static List<List<Integer>> rdg(int n, int m) throws IOException {List<List<Integer>> g = g(n); for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1); return g;}
    // static void rdg(List<List<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1);}
    // static List<Set<Integer>> rsg(int n, int m) throws IOException {List<Set<Integer>> g = sg(n); for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1); return g;}
    // static void rsg(List<Set<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1);}
    // static List<Set<Integer>> rdsg(int n, int m) throws IOException {List<Set<Integer>> g = sg(n); for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1); return g;}
    // static void rdsg(List<Set<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1);}
    // output
    static void pr(int i) {pw.print(i);}
    static void prln(int i) {pw.println(i);}
    static void pr(long l) {pw.print(l);}
    static void prln(long l) {pw.println(l);}
    static void pr(double d) {pw.print(d);}
    static void prln(double d) {pw.println(d);}
    static void pr(char c) {pw.print(c);}
    static void prln(char c) {pw.println(c);}
    static void pr(char[] s) {pw.print(new String(s));}
    static void prln(char[] s) {pw.println(new String(s));}
    static void pr(String s) {pw.print(s);}
    static void prln(String s) {pw.println(s);}
    static void pr(Object o) {pw.print(o);}
    static void prln(Object o) {pw.println(o);}
    static void prln() {pw.println();}
    static void pryes() {prln("yes");}
    static void pry() {prln("Yes");}
    static void prY() {prln("YES");}
    static void prno() {prln("no");}
    static void prn() {prln("No");}
    static void prN() {prln("NO");}
    static void pryesno(boolean b) {prln(b ? "yes" : "no");};
    static void pryn(boolean b) {prln(b ? "Yes" : "No");}
    static void prYN(boolean b) {prln(b ? "YES" : "NO");}
    static void prln(int... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static void prln(long... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static void prln(double... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for (int i = 0; i < n; pr(iter.next()), pr(' '), ++i); if (n >= 0) prln(iter.next()); else prln();}
    static void h() {prln("hlfd"); flush();}
    static void flush() {pw.flush();}
    static void close() {pw.close();}
static boolean arr[] = sieve(1000001);
static int mod = (int) (1e9+7);
static ArrayList<Long> primes = new ArrayList<>();
static ArrayList<Integer> divisors = new ArrayList<>();
static ArrayList<Integer> perfectSquares = new ArrayList<>();

// double a = 0.9;
// Setting the precision to 20 places
//     System.out.println(String.format("%.20f", a)); -> 0.99999999999999990000
//     double b = 1;
//     System.out.println(String.format("%.5f", b))  OR pn("%.5f",b); -> 1.00000

// **********************Code Begins From Here*********************

        public static void solve()
        {
            // ArrayList<Integer> al = new ArrayList<>();
            // Map<Integer,Integer> map = new HashMap<>();
            // Set<Integer> set = new TreeSet<>();
            // for(Map.Entry<Integer,Integer> e:map.entrySet())pn(e.getKey()+" "+e.getValue());
            // LinkedList<Integer> ll = new LinkedList<>();
            // Stack<Integer>st = new Stack<>();
            
            int n = sc.i(),a[][] = new int[n][n],c=0;

            for(int i=0;i<n;i++)
            {
                String s = sc.next();
                for(int j=0;j<n;j++)
                {
                    if(s.charAt(j)=='S'||s.charAt(j)=='F')a[i][j]=-1;
                    else a[i][j]=s.charAt(j)-48;
                }
            }
            String s = "", s2 = "";
            int x[] = {a[0][1]-'0', a[1][0]-'0', a[n - 2][n - 1]-'0', a[n - 1][n - 2]-'0'};
            if(x[0]==x[1]&&x[1]==x[2]&&x[2]==x[3]) {c=2; s="1 2"; s2="2 1";}
            else if(x[0]+x[1]==x[2]+x[3]) {c=2; s="2 1"; if(x[1]==x[2]) s2= n+" "+(n-1); else s2=(n-1)+" "+n;}
            else if(x[0]!=x[1]) {c=1; if(x[0]==x[3]) s="1 2"; else s="2 1";}
            else if(x[2]!=x[3]) {c=1; if(x[2]==x[0]) s=(n-1)+" "+n; else s=n+" "+(n-1);}
            System.out.println(s!=""?c+"\n"+s+(s2!=""?"\n"+s2:""):c);
        }
            public static void main(String[] args) throws FileNotFoundException {
//	        Scanner sc = new Scanner(System.i)n);
            sc = new FastScanner();
            pw = new PrintWriter(System.out);
            for(long i=0;i<arr.length;i++)
            {
                if(arr[(int)i])
                {
                    primes.add(i);
                }
            }
            int tc = sc.i(); 
            for(int t=0;t<tc;t++)
            {
                // p("Case #"+(t+1)+": ");
                solve();
            }
            pw.close();
        }

        // public static int solve(int a[],int l , int r) {
		
        //     for(int i=l+1;i<r;i++) {
        //         if(a[i]<a[i-1]) {
        //             int mid = (l+r)/2;
        //             return Math.max(solve(a,l,mid),solve(a,mid,r));
        //         }
        //     }
        //     return r-l;
        // }
          static int LCSubStr(char X[], char Y[],int m, int n)
          {
                // Create a table to store
                // lengths of longest common
                // suffixes of substrings.
                // Note that LCSuff[i][j]
                // contains length of longest
                // common suffix of
                // X[0..i-1] and Y[0..j-1].
                // The first row and first
                // column entries have no
                // logical meaning, they are
                // used only for simplicity of program
                int LCStuff[][] = new int[m + 1][n + 1];
        
                // To store length of the longest
                // common substring
                int result = 0;
        
                // Following steps build
                // LCSuff[m+1][n+1] in bottom up fashion
                for (int i = 0; i <= m; i++)
                {
                    for (int j = 0; j <= n; j++)
                    {
                        if (i == 0 || j == 0)
                            LCStuff[i][j] = 0;
                        else if (X[i - 1] == Y[j - 1])
                        {
                            LCStuff[i][j]
                                = LCStuff[i - 1][j - 1] + 1;
                            result = Integer.max(result,
                                                LCStuff[i][j]);
                        }
                        else
                            LCStuff[i][j] = 0;
                    }
                }
                return result;
            }

        static boolean number_Is_Divisible_By_Its_Digits(long n)
        {
            long temp=n;
            while(temp>0)
            {
                long digit = temp%10;
                temp/=10;
                if(digit!=0&&n%digit!=0)return false;
            }
            return true;
        }
        static int countDivisors(int n)
        {
            int cnt = 0;
            for(int i=1;i*i<=n;i++)
            {
                if(n%i==0)cnt++;
                divisors.add(i);
            }
            return cnt;
        }

        static ArrayList<Integer> countDivisorsList(int n)
        {
            for(int i=1;i*i<=n;i++)
            {
                if(n%i==0)
                divisors.add(i);
            }
            return divisors;
        }

        static boolean isStringSorted(String s)
        {
            for(int i=0;i<s.length()-1;i++)
            {
                if(s.charAt(i)>s.charAt(i+1))return false;
            }
            return true;
        }

        static boolean isPalindromeString(String s)
        {
            String temp = "";
            for(int i=s.length()-1;i>=0;i--)
            {
                temp+=s.charAt(i)+"";
            }
            return ((s.equals(temp))?true:false);
        }
        static boolean isSorted(int[] a)
        {
            int n = a.length;
            for(int i=1;i<n;i++)
            {
                if(a[i-1]>=a[i])return false;
            }
            return true;
        }
        static boolean solution(int n,int x)
        {
            int sum=0;
            while(n>0)
            {
                int digit=n%10;
                n/=10;
                sum+=digit;
            }
            return (sum==x)?true:false;
        }
        static ArrayList<Integer> perfectSquares(int n) 
        { 
            ArrayList<Integer> al = new  ArrayList<Integer>();
            for(int i=1;i<=n;i++)
            {
                al.add(i*i);
            }
            return al; 
        } 
    static boolean checkDuplicateAll(String s)
    {
        for(int i=1;i<s.length();i++)
        {
            if(s.charAt(i)!=s.charAt(i-1))return false;
        }
        return true;
    }
    static String reverseString(String s,int x)
    {
        String ans="",temp = s.substring(0,x);
        for(int i=x;i<s.length();i++)
        {
            ans = s.charAt(i)+ans;
        }
        return temp+ans;
    }
    static boolean checker(int num)
    {
        String s = num+"";
        if(s.contains("0"))return false;
        int temp = num;
        while(num>0)
        {
            int digit = num%10;
            num/=10;
            if(temp%digit==0)return false;
        }
        return true;
    }
    static boolean palindrome(int n)
    {
        int temp=n,rev=0;
        while(n>0)
        {
            int digit=n%10;
            n/=10;
            rev = rev*10+digit;
        }
        return (temp==rev)?true:false;
    }
    
    static boolean checkparanthesis(String s)
    {
        Stack<Character>st = new Stack<>();
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            if(s.charAt(i)=='(')st.push('(');
            else
            {
                if(st.size()==0)return false;
                else st.pop();
            }
        }
        return (st.size()==0)?true:false;
    }
    // static int[] reverse(int a[]){

    //     for(int i=0;i<a.length/2;i++)
    //     {
    //        int temp = a[i];
    //        a[i] = a[a.length-i-1];
    //        a[a.length-i-1] = temp;
    //     }
    //     return a;
    //     }
   static boolean[] sieve(int n)
   {
   	boolean[] isPrime = new boolean[n+1];
   	Arrays.fill(isPrime,true);
   	isPrime[0]=false;
   	isPrime[1]=false;
   	for(int i=2;i*i<=n;i++)
   	{
   		for(int j=i*i;j<=n;j+=i)
   		{
   			isPrime[j]=false;
   		}
   	}
   	return isPrime;
   }
   static int[][] graph(int from[], int to[], int n)
   {
       int g[][] = new int[n][];
       int cnt[] = new int[n];
       for (int i = 0; i < from.length; i++) {
           cnt[from[i]]++;
           cnt[to[i]]++;
       }
       for (int i = 0; i < n; i++) {
           g[i] = new int[cnt[i]];
       }
       Arrays.fill(cnt, 0);
       for (int i = 0; i < from.length; i++) {
           g[from[i]][cnt[from[i]]++] = to[i];
           g[to[i]][cnt[to[i]]++] = from[i];
       }
       return g;
   }
   
   static class Pair implements Comparable<Pair>{

       int x,y,z;
       
       Pair (int x,int y,int z){
           this.x=x;
           this.y=y;
           this.z=z;
       }
           
       public int compareTo(Pair o) {
           if (this.x == o.x)
               return Integer.compare(this.y,o.y);
           return Integer.compare(this.x,o.x);
           //return 0;
       }

       public boolean equals(Object o) {
           if (o instanceof Pair) {
               Pair p = (Pair)o;
               return p.x == x && p.y == y;
           }
           return false;
       }
       public int hashCode() {
           return new Integer(x).hashCode() * 31 + new Integer(y).hashCode();
       }
       
       @Override
       public String toString() {
           return x + " " + y;
       }
   
   } 
   
   static String rev(String s) {
       StringBuilder sb = new StringBuilder(s);
       sb.reverse();
       return sb.toString();
   }

   static long gcd(long x, long y) {
       if (y == 0) {
           return x;
       } else {
           return gcd(y, x % y);
       }
   }

   static int gcd(int x, int y) {
       if (y == 0) {
           return x;
       } else {
           return gcd(y, x % y);
       }
   }
   
   static int abs(int a, int b) {
       return (int) Math.abs(a - b);
   }

   static long abs(long a, long b) {
       return (long) Math.abs(a - b);
   }
   static void swap(int a,int b)
   {
       int c = b;
       b=a;
       a=c;
   }
   static int max(int a, int b) {
       if (a > b) {
           return a;
       } else {
           return b;
       }
   }

   static int min(int a, int b) {
       if (a > b) {
           return b;
       } else {
           return a;
       }
   }

   static long max(long a, long b) {
       if (a > b) {
           return a;
       } else {
           return b;
       }
   }

   static long min(long a, long b) {
       if (a > b) {
           return b;
       } else {
           return a;
       }
   }

   static long pow(long n, long p, long m) {
       long result = 1;
       if (p == 0) {
           return 1;
       }
       while (p != 0) {
           if (p % 2 == 1) {
               result *= n;
           }
           if (result >= m) {
               result %= m;
           }
           p >>= 1;
           n *= n;
           if (n >= m) {
               n %= m;
           }
       }
       return result;
   }

   static long pow(long n, long p) {
       long result = 1;
       if (p == 0) {
           return 1;
       }
       if (p == 1) {
           return n;
       }
       while (p != 0) {
           if (p % 2 == 1) {
               result *= n;
           }
           p >>= 1;
           n *= n;
       }
       return result;
   }
  
   static void debug(Object... o) {
           System.out.println(Arrays.deepToString(o));
   }


    


    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() throws FileNotFoundException {
            
            if (System.getProperty("ONLINE_JUDGE") == null) {
                // Input is a file
                    br = new BufferedReader(new FileReader("input.txt")); 
    
                    // PrintWriter class prints formatted representations 
                    // of objects to a text-output stream. 
                    PrintStream pw = new PrintStream(new FileOutputStream("output.txt"));
                    System.setOut(pw);
              }
            else
            {
                // Input is System.in
                br = new BufferedReader(new InputStreamReader(System.in), 32768);
                st = null;
            }
            
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int i() {
            return Integer.parseInt(next());
        }
 
        int[] intArray(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++)
                ret[i] = i();
            return ret;
        }
 
        long l() {
            return Long.parseLong(next());
        }
 
        long[] longArray(int N) {
            long[] ret = new long[N];
            for (int i = 0; i < N; i++)
                ret[i] = l();
            return ret;
        }
 
        double d() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    
    // static class InputReader
//    {

//        private final InputStream stream;
//        private final byte[] buf = new byte[8192];
//        private int curChar, snumChars;
//        private SpaceCharFilter filter;

//        public InputReader(InputStream stream)
//        {
//                this.stream = stream;
//        }

//        public int snext()
//        {
//                if (snumChars == -1)
//                        throw new InputMismatchException();
//                if (curChar >= snumChars)
//                {
//                        curChar = 0;
//                        try
//                        {
//                                snumChars = stream.read(buf);
//                        } catch (IOException e)
//                        {
//                                throw new InputMismatchException();
//                        }
//                        if (snumChars <= 0)
//                                return -1;
//                }
//                return buf[curChar++];
//        }

//        public int nextInt()
//        {
//                int c = snext();
//                while (isSpaceChar(c))
//                {
//                        c = snext();
//                }
//                int sgn = 1;
//                if (c == '-')
//                {
//                        sgn = -1;
//                        c = snext();
//                }
//                int res = 0;
//                do
//                {
//                        if (c < '0' || c > '9')
//                                throw new InputMismatchException();
//                        res *= 10;
//                        res += c - '0';
//                        c = snext();
//                } while (!isSpaceChar(c));
//                return res * sgn;
//        }

//        public long nextLong()
//        {
//                int c = snext();
//                while (isSpaceChar(c))
//                {
//                        c = snext();
//                }
//                int sgn = 1;
//                if (c == '-')
//                {
//                        sgn = -1;
//                        c = snext();
//                }
//                long res = 0;
//                do
//                {
//                        if (c < '0' || c > '9')
//                                throw new InputMismatchException();
//                        res *= 10;
//                        res += c - '0';
//                        c = snext();
//                } while (!isSpaceChar(c));
//                return res * sgn;
//        }

//        public int[] nextIntArray(int n)
//        {
//                int a[] = new int[n];
//                for (int i = 0; i < n; i++)
//                {
//                        a[i] = nextInt();
//                }
//                return a;
//        }

//        public long[] nextLongArray(int n)
//        {
//                long a[] = new long[n];
//                for (int i = 0; i < n; i++)
//                {
//                        a[i] = nextLong();
//                }
//                return a;
//        }

//        public String readString()
//        {
//                int c = snext();
//                while (isSpaceChar(c))
//                {
//                        c = snext();
//                }
//                StringBuilder res = new StringBuilder();
//                do
//                {
//                        res.appendCodePoint(c);
//                        c = snext();
//                } while (!isSpaceChar(c));
//                return res.toString();
//        }

//        public String nextLine()
//        {
//                int c = snext();
//                while (isSpaceChar(c))
//                        c = snext();
//                StringBuilder res = new StringBuilder();
//                do
//                {
//                        res.appendCodePoint(c);
//                        c = snext();
//                } while (!isEndOfLine(c));
//                return res.toString();
//        }

//        public boolean isSpaceChar(int c)
//        {
//                if (filter != null)
//                        return filter.isSpaceChar(c);
//                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
//        }

//        private boolean isEndOfLine(int c)
//        {
//                return c == '\n' || c == '\r' || c == -1;
//        }

//        public interface SpaceCharFilter
//        {
//                public boolean isSpaceChar(int ch);
//        }
}