You have an initially empty cauldron, and you want to brew a potion in it. The potion consists of two ingredients: magic essence and water. The potion you want to brew should contain exactly k\ \% magic essence and (100 - k)\ \% water.

In one step, you can pour either one liter of magic essence or one liter of water into the cauldron. What is the minimum number of steps to brew a potion? You don't care about the total volume of the potion, only about the ratio between magic essence and water in it.

A small reminder: if you pour e liters of essence and w liters of water (e + w > 0) into the cauldron, then it contains (e)/(e + w) ⋅ 100\ \% (without rounding) magic essence and (w)/(e + w) ⋅ 100\ \% water.

Input

The first line contains the single t (1 ≤ t ≤ 100) — the number of test cases.

The first and only line of each test case contains a single integer k (1 ≤ k ≤ 100) — the percentage of essence in a good potion.

Output

For each test case, print the minimum number of steps to brew a good potion. It can be proved that it's always possible to achieve it in a finite number of steps.

Example

Input


3
3
100
25


Output


100
1
4

Note

In the first test case, you should pour 3 liters of magic essence and 97 liters of water into the cauldron to get a potion with 3\ \% of magic essence.

In the second test case, you can pour only 1 liter of essence to get a potion with 100\ \% of magic essence.

In the third test case, you can pour 1 liter of magic essence and 3 liters of water.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.math.BigInteger;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Dragons {
	 
    static class Pair {
        long a;
        long b;
        public Pair(long a, long b){
            this.a=a;
            this.b=b;
        }
    }
	static ArrayList<Integer>[]adjList;
	static boolean[] color;
	static boolean visited[];
	
	public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t>0) {
int a=sc.nextInt();
reduceFraction(a,100);
	
	t--;
}
	}
	static boolean isInteger(double N)
	{
	 
	    // Convert float value
	    // of N to integer
	    long X = (long)N;
	    double temp2 = N - X;
	 
	    // If N is not equivalent
	    // to any integer
	    if (temp2 > 0)
	    {
	        return false;
	    }
	    return true;
	}
	static long isrecursive(long p) {
		if(p==0) {
			return 0;
		}else if(p%2==0) {
			return isrecursive(p/2);
		}else {
			return isrecursive(p/2)+1;
		}
		
	}
	static int islucky(int r) {
		String temp = Integer.toString(r);
		int[] newGuess = new int[temp.length()];
		int tu=0;
		for (int i = 0; i < temp.length(); i++)
		{
		    newGuess[i] = temp.charAt(i) - '0';
		    if(newGuess[i]==4 || newGuess[i]==7) {
		    	tu=tu*10+newGuess[i];
		    }
		}
		return tu;
	}
	static int distance(long l,long m) {
		return (int) (Math.pow(l,2)+Math.pow(m,2));
	}
	static int findSmallest(int N)
	{
	  
	    // Base case
	    if (N == 0)
	        return 2;
	    if (N == 1)
	        return 1;
	  
	    int prime = N, counter = 0;
	    boolean found = false;
	  
	    // Loop continuously until isPrime returns
	    // true for a number greater than n
	    while (!found) {
	        if (isPrime(prime))
	            found = true;
	        else {
	  
	            // If the number is not a prime, then
	            // increment the number by 1 and the
	            // counter which stores the number
	            // to be added
	            prime++;
	            counter++;
	        }
	    }
	  
	    return counter;
	}
	static boolean isPrime(int n)
	{
	    // Base cases
	    if (n <= 1)
	        return false;
	    if (n <= 3)
	        return true;
	  
	    // This is checked so that we can skip
	    // middle five numbers in below loop
	    if (n % 2 == 0 || n % 3 == 0)
	        return false;
	  
	    // For all the remaining numbers, check if
	    // any number is a factor if the number
	    // or not
	    for (int i = 5; i * i <= n; i = i + 6)
	        if (n % i == 0 || n % (i + 2) == 0)
	            return false;
	  
	    // If none of the above numbers are the
	    // factors for the number, then the
	    // given number is prime
	    return true;
	}
	
	
		static int mod(int a, int m)
		{
		    return (a%m + m) % m;
		}
		
	static long getSum(long y)
    {
       long sum = 0;
 
        while (y != 0) {
            sum = sum + y % 10;
            y = y / 10;
        }
 
        return sum;
    }
	static boolean detect(int arr[],int x) {
		long sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum==x) {
				return true;
			}
			
		}
		return false;
	}
	
    static class Node {
        String s;
        int val;
 
        public Node(String a, int v) {
            val = v;
            s = a;
        }
    }
	  
	 public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<String, Integer> > list =
	               new LinkedList<Map.Entry<String, Integer> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() {
	            public int compare(Map.Entry<String, Integer> o1,
	                               Map.Entry<String, Integer> o2)
	            {
	                return -(o1.getValue()).compareTo(o2.getValue());
	            }
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>();
	        for (Map.Entry<String, Integer> aa : list) {
	            temp.put(aa.getKey(), aa.getValue());
	        }
	        return temp;
	    }
	
 
static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
static void reduceFraction(int x, int y) 
{ 
    int d; 
    d = gcd(x, y); 
  
    x = x / d; 
    y = y / d; 
  if(x>0 && y<0) {
	  x=-x;
	  y=-y;
  }
    System.out.println(y); 
} 
	
	static int gcd(int a, int b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	
	static boolean[] sieve(int n) {
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		}
		return isPrime;
		
	}
}