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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author zodiacLeo
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        FastPrinter out = new FastPrinter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
    
    static class TaskC {
        public void solve(int testNumber, FastScanner in, FastPrinter out) {
            String a = "Ashishgup\n";
            String b = "FastestFinger\n";
            
            StringBuilder result = new StringBuilder();
            
            int T = in.nextInt();
            while (T-- > 0) {
                
                int n = in.nextInt();
                if (n == 1) {
                    result.append(b);
                    continue;
                }
                if (n == 2) {
                    result.append(a);
                    continue;
                }
                if (n % 2 != 0) {
                    result.append(a);
                    continue;
                }
                
                int[] factors = countPrimeFactors(n);
                int countEven = factors[0];
                int countOdd = factors[1];
                if (countEven > 0 && countOdd == 0) {
                    result.append(b);
                    continue;
                }
                if (countEven == 1) {
                    if (countOdd == 1) {
                        result.append(b);
                        continue;
                    }
                    else {
                        result.append(a);
                        continue;
                    }
                }
                
                result.append(a);
            }
            out.println(result);
        }
        
        private int[] countPrimeFactors(int n) {
            int countEven = 0;
            int countOdd = 0;
            for (int i = 2; i * i <= n; i++) {
                while (n % i == 0) {
                    if (i % 2 == 0) {
                        countEven++;
                    }
                    else {
                        countOdd++;
                    }
                    n /= i;
                }
            }
            if (n > 1) {
                countOdd++;
            }
            return new int[]{countEven, countOdd};
        }
        
    }
    
    static class FastPrinter extends PrintWriter {
        public FastPrinter(OutputStream out) {
            super(out);
        }
        
        public FastPrinter(Writer out) {
            super(out);
        }
        
    }
    
    static class FastScanner {
        public BufferedReader br;
        public StringTokenizer st;
        
        public FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        
        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        
        public String next() {
            while (st == null || !st.hasMoreElements()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null) {
                    return null;
                }
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
    }
}

