Ashishgup and FastestFinger play a game. 

They start with a number n and play in turns. In each turn, a player can make any one of the following moves:

  * Divide n by any of its odd divisors greater than 1. 
  * Subtract 1 from n if n is greater than 1. 



Divisors of a number include the number itself.

The player who is unable to make a move loses the game.

Ashishgup moves first. Determine the winner of the game if both of them play optimally.

Input

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

The only line of each test case contains a single integer — n (1 ≤ n ≤ 10^9).

Output

For each test case, print "Ashishgup" if he wins, and "FastestFinger" otherwise (without quotes).

Example

Input


7
1
2
3
4
5
6
12


Output


FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup

Note

In the first test case, n = 1, Ashishgup cannot make a move. He loses.

In the second test case, n = 2, Ashishgup subtracts 1 on the first move. Now n = 1, FastestFinger cannot make a move, so he loses.

In the third test case, n = 3, Ashishgup divides by 3 on the first move. Now n = 1, FastestFinger cannot make a move, so he loses.

In the last test case, n = 12, Ashishgup divides it by 3. Now n = 4, FastestFinger is forced to subtract 1, and Ashishgup gets 3, so he wins by dividing it by 3.
 
 import java.io.*;
 import java.util.*;
 import java.math.*;
 
 public class Main { 
     
     public static void main(String[] args) throws java.lang.Exception { 
         Reader pm =new Reader(); 
         //Scanner pm = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
         int t = pm.nextInt();
         while(t-- > 0){
             long n = pm.nextLong();
             if(n == 1) {
                System.out.println("FastestFinger");
                continue;
             }
             if(n == 2) {
                System.out.println("Ashishgup");
                continue;
             }
             if(n % 2 == 1) {
                System.out.println("Ashishgup");
             } else {
                double pow = Math.log(n)/ Math.log(2);
                //System.out.println(pow);
                if((n & (n-1)) == 0) {
                    System.out.println("FastestFinger");
                } else {
                    if(n % 4 == 0) {
                        System.out.println("Ashishgup");
                    } else {
                        if(!isNotPrime(n/2))
                            System.out.println("FastestFinger");
                        else
                            System.out.println("Ashishgup");
                    }
                }
             }
             //System.out.println(n & (n-1));
         }
         //end of tests
         
     }
     //end of main class
    public static boolean isNotPrime(long n) {
        for(int i = 2; i <= Math.sqrt(n); i++) 
            if(n % i == 0) return true;
        return false;
    }
     static int countInRange(int arr[], int n, int x, int y) { 
         // initialize result 
         int count = 0; 
         count = upperIndex(arr, n, y) -  
                 lowerIndex(arr, n, x) + 1; 
         return count; 
     } 
     
     
     static int lowerIndex(int arr[], int n, int x) { 
         int l = 0, h = n - 1; 
         while (l <= h)  
         { 
             int mid = (l + h) / 2; 
             if (arr[mid] >= x) 
                 h = mid - 1; 
             else
                 l = mid + 1; 
         } 
         return l; 
     } 
       
     // function to find last index <= y 
     static int upperIndex(int arr[], int n, int y) { 
         int l = 0, h = n - 1; 
         while (l <= h)  
         { 
             int mid = (l + h) / 2; 
             if (arr[mid] <= y) 
                 l = mid + 1; 
             else
                 h = mid - 1; 
         } 
         return h; 
     }
     
     public static StringBuilder dec_to_bin(long n) {
         // decimal to binary upto 30 binaries
         if(n==0) {
             StringBuilder str=new StringBuilder("");
             for(int i=0;i<30;i++) {
                 str.append("0");
             }
             return str;
         }
         StringBuilder str=new StringBuilder("");
         while(n!=0) {
             str.append(n%2L);
             n/=2L;
         }
         str=str.reverse();
         StringBuilder tmp_str=new StringBuilder("");
         int len=str.length();
         while(len!=30) {
             tmp_str.append("0");
             len++;
         }
         tmp_str.append(str);
         return tmp_str;
     }
     
     private static int binarySearchPM(int[] arr, int key){
         int n = arr.length;
         int mid = -1;
         int begin = 0,end=n;
         while(begin <= end){
             mid = (begin+end) / 2;
             if(mid == n){
                 return n;
             }
             if(key < arr[mid]){
                 end = mid-1;
             } else if(key > arr[mid]){
                 begin = mid+1;
             } else {
                 return mid;
             }
         }
         //System.out.println(begin+" "+end);
         return -begin; //expected Index
     }
     
     static class Reader { 
         final private int BUFFER_SIZE = 1 << 16; 
         private DataInputStream din; 
         private byte[] buffer; 
         private int bufferPointer, bytesRead; 
   
         public Reader() 
         { 
             din = new DataInputStream(System.in); 
             buffer = new byte[BUFFER_SIZE]; 
             bufferPointer = bytesRead = 0; 
         } 
   
         public Reader(String file_name) throws IOException 
         { 
             din = new DataInputStream(new FileInputStream(file_name)); 
             buffer = new byte[BUFFER_SIZE]; 
             bufferPointer = bytesRead = 0; 
         } 
   
         public String readLine() throws IOException 
         { 
             byte[] buf = new byte[64]; // line length 
             int cnt = 0, c; 
             while ((c = read()) != -1) 
             { 
                 if (c == '\n') 
                     break; 
                 buf[cnt++] = (byte) c; 
             } 
             return new String(buf, 0, cnt); 
         } 
   
         public int nextInt() throws IOException 
         { 
             int ret = 0; 
             byte c = read(); 
             while (c <= ' ') 
                 c = read(); 
             boolean neg = (c == '-'); 
             if (neg) 
                 c = read(); 
             do
             { 
                 ret = ret * 10 + c - '0'; 
             }  while ((c = read()) >= '0' && c <= '9'); 
   
             if (neg) 
                 return -ret; 
             return ret; 
         } 
   
         public long nextLong() throws IOException 
         { 
             long ret = 0; 
             byte c = read(); 
             while (c <= ' ') 
                 c = read(); 
             boolean neg = (c == '-'); 
             if (neg) 
                 c = read(); 
             do { 
                 ret = ret * 10 + c - '0'; 
             } 
             while ((c = read()) >= '0' && c <= '9'); 
             if (neg) 
                 return -ret; 
             return ret; 
         } 
   
         public double nextDouble() throws IOException 
         { 
             double ret = 0, div = 1; 
             byte c = read(); 
             while (c <= ' ') 
                 c = read(); 
             boolean neg = (c == '-'); 
             if (neg) 
                 c = read(); 
   
             do { 
                 ret = ret * 10 + c - '0'; 
             } 
             while ((c = read()) >= '0' && c <= '9'); 
   
             if (c == '.') 
             { 
                 while ((c = read()) >= '0' && c <= '9') 
                 { 
                     ret += (c - '0') / (div *= 10); 
                 } 
             } 
   
             if (neg) 
                 return -ret; 
             return ret; 
         } 
   
         private void fillBuffer() throws IOException 
         { 
             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
             if (bytesRead == -1) 
                 buffer[0] = -1; 
         } 
   
         private byte read() throws IOException 
         { 
             if (bufferPointer == bytesRead) 
                 fillBuffer(); 
             return buffer[bufferPointer++]; 
         } 
   
         public void close() throws IOException 
         { 
             if (din == null) 
                 return; 
             din.close(); 
         } 
     }
 }    