Alice has just learned addition. However, she hasn't learned the concept of "carrying" fully — instead of carrying to the next column, she carries to the column two columns to the left.

For example, the regular way to evaluate the sum 2039 + 2976 would be as shown: 

<image>

However, Alice evaluates it as shown: 

<image>

In particular, this is what she does: 

  * add 9 and 6 to make 15, and carry the 1 to the column two columns to the left, i. e. to the column "0 9"; 
  * add 3 and 7 to make 10 and carry the 1 to the column two columns to the left, i. e. to the column "2 2"; 
  * add 1, 0, and 9 to make 10 and carry the 1 to the column two columns to the left, i. e. to the column above the plus sign; 
  * add 1, 2 and 2 to make 5; 
  * add 1 to make 1. 

Thus, she ends up with the incorrect result of 15005.

Alice comes up to Bob and says that she has added two numbers to get a result of n. However, Bob knows that Alice adds in her own way. Help Bob find the number of ordered pairs of positive integers such that when Alice adds them, she will get a result of n. Note that pairs (a, b) and (b, a) are considered different if a ≠ b.

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases. The description of the test cases follows.

The only line of each test case contains an integer n (2 ≤ n ≤ 10^9) — the number Alice shows Bob.

Output

For each test case, output one integer — the number of ordered pairs of positive integers such that when Alice adds them, she will get a result of n. 

Example

Input


5
100
12
8
2021
10000


Output


9
4
7
44
99

Note

In the first test case, when Alice evaluates any of the sums 1 + 9, 2 + 8, 3 + 7, 4 + 6, 5 + 5, 6 + 4, 7 + 3, 8 + 2, or 9 + 1, she will get a result of 100. The picture below shows how Alice evaluates 6 + 4: 

<image>
import java.util.*;
import java.io.*;
public class Test {
	public static void main(String[] args) throws IOException {
	   Scanner sc = new Scanner(System.in);
	   PrintWriter pw = new PrintWriter(System.out);
	   int t = sc.nextInt();
	   int [] xor = new int[400005] ;
	   for(int i = 1;i<xor.length;i++) {
		   xor[i]=xor[i-1]^i;
	   }
	   while(t-->0) {
		   String  s = sc.next();
		  String odd = "";
		  String even = "";
		  for(int i = 0;i<s.length();i++) {
			  if(i%2==0) {
				  even+=s.charAt(i);
			  }
			  else {
				  odd+=s.charAt(i);
			  }
		  }
		 // System.out.println(odd);
		  long oddNum = (odd.length()>0)?Long.parseLong(odd):0;
		  long evenNum = Long.parseLong(even);
		  long ans = (oddNum+1)*(evenNum+1)-2;
		  System.out.println(ans);
	     
	  }}
	static void bfs(int s) {
		
	    parent[s]=-1;
	    Queue<Integer> q = new LinkedList<Integer>();
		q.add(s);
		visited[s] = true;
		while(!q.isEmpty()) {
			int u = q.poll();
			
			//System.out.println("u"+" "+u);
			for(int v : adjList[u]) {
				//System.out.println("v"+" "+v);

				if(!visited[v]) {
					q.add(v);
					parent[v] = u;
					distance[v] = 1+distance[u];
					visited[v]=true;
					if(v==n-1) {
						return;
					}
				}
				
			}}
		
		
		
		

		
	}static ArrayList<Integer> ans;
	static int d1;
		   static class triple {
	            int u;
	            int v;
	            int z;
	 
	            public triple(int u, int v, int z) {
	                this.u = u;
	                this.v = v;
	                this.z = z;
	            }
	 
	            public String toString() {
	                return "triple{" +
	                        "u=" + u +
	                        ", v=" + v +
	                        ", z=" + z +
	                        '}';
	            }
	 
	            public boolean equals(Object o) {
	                if (this == o) return true;
	                if (o == null || getClass() != o.getClass()) return false;
	                triple triple = (triple) o;
	                return u == triple.u &&
	                        v == triple.v &&
	                        z == triple.z;
	            }
	 
	            public int hashCode() {
	                return Objects.hash(u, v, z);
	            }}
	 

	static int [] distance; 
	static  ArrayList<Integer> [] adjList ;
	
	static HashMap<Pair,Integer> hm;
	static boolean [] visited;
	static int [] parent;
	public static boolean check (int a) {
		if(a==2) {
			return true;
		}
		ArrayList <Integer> indices = new ArrayList<Integer>();
		for (int i = 0;i<arr.length;i++) {
			if (arr[i] <= a) {
				indices.add(i);
			}}
		boolean first = false;
		ArrayList<Integer> jumps = new ArrayList<Integer>();
		for(int i = 0;i<indices.size()-1;i++) {
			//System.out.println(indices.get(i+1));
			if (indices.get(i+1)-indices.get(i)>1) {
				jumps.add(indices.get(i+1)-indices.get(i));
				
				
			}
		}
		
		if (jumps.size()==0||(jumps.size()==2&&jumps.get(0)==2)||(jumps.size()==2&&jumps.get(1)==2)||(jumps.size()==1&&jumps.get(0)==2)||(jumps.size()==1&&a==3)){
			return true;
		}
		else {
			return false;
		}
		
			
	}
	static class Edge {
		int u ;
		int v ;
		boolean visited = false;
		ArrayList<Edge> adjList;
		public Edge  (int u , int v) {
			this.u = u;
			this.v = v;
			this.adjList = new ArrayList<Edge>();
		}
		public void add(Edge e) {
			this.adjList.add(e);
		}
	}
	static int [] arr;
	static long mod;
	public static double solve(int currTrial, int lampsMask) {
		if(lampsMask ==0 || currTrial==101) {
			return (currTrial-1);
		}
		if(dp[currTrial][lampsMask]!=-1) {
			return dp[currTrial][lampsMask];
		}
		double tot = 0;
		for(int i = 0;i<m;i++) {
			tot += (solve(currTrial+1,lampsMask^switchMask[i])/m);
		}
	    
		return dp[currTrial][lampsMask] = (tot);
		
	}
	static double [][] dp ;
	static double probFactor;
	static int m;
	static int [] switchMask;
    static int lcs(char[] X, char[] Y, int m, int n)
     {
         if (m == 0 || n == 0)
             return 0;
         if (X[m - 1] == Y[n - 1])
             return 1 + lcs(X, Y, m - 1, n - 1);
         else
             return Math.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
     }
	    public static void dfs1(int node) {
	    	visited1[node] = true;
	    	for(int v :adjLists1[node]) {
	    		if(!visited1[v]) {
	    			dfs1(v);
	    		}
	    	}
	    	
	    }
	   static int maxSubsequenceSubstring(char[] X,char[] Y,int n,int m)
	    {
	        // Base Case
	        if (n==0 || m==0) return 0;
	        
	        // Calls on smaller inputs
	        
	        // if the last char of both strings are equal
	        if(X[n-1] == Y[m-1])
	        {
	            return  1 + maxSubsequenceSubstring(X,Y,n-1,m-1);
	        }
	        
	        // if the last char of both strings are not equal
	        else
	        {
	            return maxSubsequenceSubstring(X,Y,n-1,m);    
	        }
	    }
	    public static void dfs2(int node) {
	    	visited2[node] = true;
	    	for(int v :adjLists2[node]) {
	    		if(!visited2[v]) {
	    			dfs2(v);
	    		}
	    	}
	    }
	    static class Picture implements Comparable{
	    	char [][] pixels;
	    	int numOFOnes;
	    	int idx;
	    	public Picture(char [][] pixels, int numOfOnes, int idx) {
	    		this.pixels = pixels;
	    		this.numOFOnes = numOfOnes;
	    		this.idx = idx;
	    	}
			@Override
			public int compareTo(Object arg0) {
				Picture p = (Picture) arg0;
				return numOFOnes - p.numOFOnes;
			}
	    	
	    }
	    static  ArrayList<Integer> [] adjLists1;
	    static ArrayList<Integer> [] adjLists2;
	    static boolean []visited1;
	    static boolean [] visited2;
		//static int [] arr ;
		static int d [] ;
		
	   static  HashSet<Long> hs = new HashSet<Long>();
	  
	public static int idxOf(String s,char c) {
		int idx = -2;
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==c) {
				return i;
			}
		}
		return idx;
	}
	static ArrayList<Long >start;
	static ArrayList<Long> end;
	public static void dfs (int idx) {
		can[idx] = true;
		for(int i = 0;i<start.size();i++) {
			if((start.get(i)<start.get(idx)&& end.get(i)>start.get(idx)||(start.get(i)<end.get(idx)&& end.get(i)>end.get(idx)))){
				if(!can[i]) {
				dfs(i);
			}}
		}
	}
	static boolean [] can ; 
	static int n;
	
	static int [] [] sol;
	static int [] g;
	public static void constructSol() {
		for(int i = 1;i<sol.length;i++) {
			for(int j = 1;j<10;j++) {
				if(g[i] == j) {
					sol[i][j] = sol[i-1][j]+1;
				}
				else {
					sol[i][j] = sol[i-1][j];
				}
			}
		}
	}
	public static void prod() {
		for(int i=1;i<g.length;i++) {
			int n = i;
		if(n<10) {
			g[ n] = n;
		    continue;
		}
		int prod = 1;
		while(n>0) {
			if(n%10!=0) {
				prod*= (n%10);
				
			}
			n/=10;
		}
		//System.out.println(prod);
		g[i] = g[prod];
	
	}}
	public static  boolean isPalindrome(String s) {
		
		for(int i = 0;i<=s.length()/2;i++) {
			if(s.charAt(i)!=s.charAt(s.length()-1-i)) {
				return false;
			}
		}
		return true;
	}
	public static long logBase2(long n) {
		long ans = 0;
		while(n>1) {
			ans ++;
			n/=2;
		}
		return ans;
	}
	public static double getmostLeft(ArrayList<Circle> list) {
	        double min = Double.MAX_VALUE;
	        for (Circle c: list) {
	            min = Math.min(min, c.x - c.r);
	        }
	        return min;
	    }
 
	   public static double getmostRight(ArrayList<Circle> list) {
	        double max = Double.MIN_VALUE;
	        for (Circle c: list) {
	            max = Math.max(max, c.x + c.r);
	        }
	        return max;
	    }
	static class Circle{
		double x ;
		double y ;
		double r;
		int id;
		public Circle(double x, double y, double r) {
			this.x = x;
			this.y = y;
			this.r = r;
			
		}
		public String toString () {
			return x +" "+y+" "+r;
		}
		public boolean intersect(Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
			if(dist<=r+o.r) {
				return true;
			}
			return false;
		}
		public  Circle combine( Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
		    if(Math.abs(r-o.r)>=dist) {
		    	if(r>=o.r) {
		    		return this;
		    	}
		    	else {
		    		return o;
		    	}
		    }
 
			double cx = (x+o.x)/2.0;
			double cy = (y+o.y)/2.0;
			double rad = (dist +r +this.r)/2.0;
			return new Circle (cx, cy, rad);
		}
	}
	static class Pair {
		int x;
		int y;
		public Pair (int x, int y) {
			this.x = x;
			this.y = y;
			
		}
		public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair triple = (Pair) o;
            return x == triple.x &&
                    y == triple.y ;
        }
	}
	public static String solve (String s) {
		Stack <String> st = new Stack<String>();
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==']') {
				String toEncode = "";
				while(!st.isEmpty()&&!st.peek().equals("[")) {
					toEncode = st.pop()+ toEncode;
				}
				st.pop();
				String toPush = "";
				int freq = Integer.parseInt(st.pop());
				while(freq-->0) {
					toPush+=toEncode;
				}
				st.push(toPush);
			}
			else {
				st.push(s.charAt(i)+"");
			}
			
		}
		String res = "";
		while(!st.isEmpty()) {
			res = st.pop() +res;
		}
		return res;
	}
	static String alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
	static String s;
	static ArrayList <Integer> prime;
	 static void simpleSieve(int limit)
	    {   
	        // Create a boolean array "mark[0..n-1]" and initialize
	        // all entries of it as true. A value in mark[p] will
	        // finally be false if 'p' is Not a prime, else true.
	        boolean mark[] = new boolean[limit+1];
	         
	        for (int i = 0; i < mark.length; i++)
	            mark[i] = true;
	      
	        for (int p=2; p*p<limit; p++)
	        {
	            // If p is not changed, then it is a prime
	            if (mark[p] == true)
	            {
	                // Update all multiples of p
	                for (int i=p*p; i<limit; i+=p)
	                    mark[i] = false;
	            }
	        }
	      
	        // Print all prime numbers and store them in prime
	        for (int p=2; p<limit; p++)
	        {
	            if (mark[p] == true)
	            {
	                prime.add(p);
	               // System.out.print(p + "  ");
	            }
	        }
	    }
 
	 
	 public static long gcd (long a, long b ) {
		 if(b==0) {
			 return a;
		 }
		 else {
			 return gcd (b, a%b);
		 }
	 }
	 
 static class Scanner {
 		StringTokenizer st;
 		BufferedReader br;
  
 		public Scanner(InputStream s) {
 			br = new BufferedReader(new InputStreamReader(s));
 		}
        public Scanner(FileReader r) {
        	br = new BufferedReader(r);
        }
 		public boolean hasNext() {
 			// TODO Auto-generated method stub
 			return false;
 		}
  
 		public String next() throws IOException {
 			while (st == null || !st.hasMoreTokens())
 				st = new StringTokenizer(br.readLine());
 			return st.nextToken();
 		}
  
 		public int nextInt() throws IOException {
 			return Integer.parseInt(next());
 		}
  
 		public long nextLong() throws IOException {
 			return Long.parseLong(next());
 		}
  
 		public String nextLine() throws IOException {
 			return br.readLine();
 		}
  
 		public double nextDouble() throws IOException {
 			String x = next();
 			StringBuilder sb = new StringBuilder("0");
 			double res = 0, f = 1;
 			boolean dec = false, neg = false;
 			int start = 0;
 			if (x.charAt(0) == '-') {
 				neg = true;
 				start++;
 			}
 			for (int i = start; i < x.length(); i++)
 				if (x.charAt(i) == '.') {
 					res = Long.parseLong(sb.toString());
 					sb = new StringBuilder("0");
 					dec = true;
 				} else {
 					sb.append(x.charAt(i));
 					if (dec)
 						f *= 10;
 				}
 			res += Long.parseLong(sb.toString()) / f;
 			return res * (neg ? -1 : 1);
 		}
  
 		public boolean ready() throws IOException {
 			return br.ready();
 		}
  
 	}
}