Problem: A robot is standing at the origin of the infinite two-dimensional plane. Each second the robot moves exactly 1 meter in one of the four cardinal directions: north, south, west, and east. For the first step the robot can choose any of the four directions, but then at the end of every second it has to turn 90 degrees left or right with respect to the direction it just moved in. For example, if the robot has just moved north or south, the next step it takes has to be either west or east, and vice versa.

The robot makes exactly n steps from its starting position according to the rules above. How many different points can the robot arrive to at the end? The final orientation of the robot can be ignored.

Input

The only line contains a single integer n (1 ≤ n ≤ 1000) — the number of steps the robot makes.

Output

Print a single integer — the number of different possible locations after exactly n steps.

Examples

Input


1


Output


4


Input


2


Output


4


Input


3


Output


12

Note

In the first sample case, the robot will end up 1 meter north, south, west, or east depending on its initial direction.

In the second sample case, the robot will always end up √{2} meters north-west, north-east, south-west, or south-east.

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Mamo {
	//  Solution 
    public static void main(String [] args) throws IOException {
    	//Dir by MohammedElkady
    	int tt=1;
    	while(tt-->0) {
    		long ans=0L;
    		int n=in.nextInt();
    		int a[][]=new int[n+1003][n+1003];
    		int l=(n/2)+1000,r=((n+1)/2)+1000,ll=n/2,rr=((n+1)/2),rl=r;
    		for(int i=0;i<ll+1;i++) {
    			for (int j = 0; j < rr+1; j++) {
    				//System.out.println(l+" "+r);
    				if(a[l][r]==0)
    					ans++;
					a[l][r]++;
    				r-=2;
				}
    			r=rl;
    			l-=2;
    		}
    		if(n%2==1) {
    			 l=(n+1/2)+1000;r=((n)/2)+1000;ll=(n+1)/2;rr=((n)/2);rl=r;
    	    		for(int i=0;i<ll+1;i++) {
    	    			for (int j = 0; j < rr+1; j++) {
    	    				if(a[l][r]==0)
    	    					ans++;
    						a[l][r]++;
    	    				r-=2;
    					}
    	    			r=rl;
    	    			l-=2;
    	    		}
    		}
    	out.append(ans+" ");
    	}
	out.close();
        
    }
    static StringBuilder Sd=new StringBuilder();
    static Reader in=new Reader();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}
class node {

int i;
String name;
node(String S,int ll){
i=ll;
name=S;
}

}
class xtree{
	public xtree(int n,int a[]) {
		this.a=a;
		seg=new int[n*4];
		//lazy=new int[n*4];
		build(1,0,n-1);
	}
	int seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        //check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = seg[2*p]+ seg[2*p+1];
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	       // check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        //check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
    
 
    
    int get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return 0; 
        
        return get(2*p,s,(s+e)/2,a,b)+ get(2*p+1,(s+e)/2+1,e,a,b);
    }
}

class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}
 class LongestCommonSubsequence 
{ 
  
  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	 int lcs( char[] X, char[] Y, int m, int n ,int K) 
	  { 
		 int L[][] = new int[m+1][n+1]; 
		 int ans[][]=new int[m+1][n+1];
		 int min[][] = new int[m+1][n+1]; 
		 for(int i=0;i<=n;i++) 
			 for(int j=0;j<=m;j++) 
				 min[j][i]='z'+1;
	    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	    for (int i=0; i<=m; i++) 
	    { 
	      for (int j=0; j<=n; j++)
	      { 
	        if (i == 0 || j == 0) 
	            L[i][j] = 0; 
	        else if (X[i-1] == Y[j-1]) { 
	            L[i][j] = L[i-1][j-1] + 1; 
	            ans[i][j]=ans[i-1][j-1]+X[i-1];
	         
	        }
	        else {
	            L[i][j] = max(L[i-1][j], L[i][j-1]); }
	      } 
	    } 
	  return L[m][n]; 
	  } 
	  
	  /* Utility function to get max of 2 integers */
	  int max(int a, int b) 
	  { 
	    return (a > b)? a : b; 
	  } 

     // Returns length of LCS for X[0..m-1], Y[0..n-1] 
     static String lcs(String X, String Y, int m, int n) 
     { 
         int[][] L = new int[m+1][n+1]; 
    
         // Following steps build L[m+1][n+1] in bottom up fashion. Note 
         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]  
         for (int i=0; i<=m; i++) 
         { 
             for (int j=0; j<=n; j++) 
             { 
                 if (i == 0 || j == 0) 
                     L[i][j] = 0; 
                 else if (X.charAt(i-1) == Y.charAt(j-1)) 
                     L[i][j] = L[i-1][j-1] + 1; 
                 else
                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]); 
             } 
         } 
    
         // Following code is used to print LCS 
         int index = L[m][n]; 
         int temp = index; 
    
         // Create a character array to store the lcs string 
         char[] lcs = new char[index+1]; 
         lcs[index] = '\u0000'; // Set the terminating character 
    
         // Start from the right-most-bottom-most corner and 
         // one by one store characters in lcs[] 
         int i = m; 
         int j = n; 
         while (i > 0 && j > 0) 
         { 
             // If current character in X[] and Y are same, then 
             // current character is part of LCS 
             if (X.charAt(i-1) == Y.charAt(j-1)) 
             { 
                 // Put current character in result 
                 lcs[index-1] = X.charAt(i-1);  
                   
                 // reduce values of i, j and index 
                 i--;  
                 j--;  
                 index--;      
             } 
    
             // If not same, then find the larger of two and 
             // go in the direction of larger value 
             else if (L[i-1][j] > L[i][j-1]) 
                 i--; 
             else
                 j--; 
         } 
    
         // Print the lcs 
         StringBuilder Sd=new StringBuilder();
         for(int k=0;k<=temp;k++) 
             Sd.append(lcs[k]); 
      return Sd.toString();   
     }
 }