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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;

public class C {
    private static HashMap<String , Boolean> dp;
    private static boolean isFirstWinner(int n, int turn){
        if(n == 1 && turn == 1) return false;
        if(n == 1 && turn == 2) return true;
        String key = n +":"+ turn;
        if(dp.get(key) != null) return dp.get(key);
        if(turn == 1){
            boolean winner = false;
            if(n % 2 == 1) {
                winner = winner || isFirstWinner(1, 2);
                if(winner){
                    dp.put(key, winner);
                    return winner;
                }
            }
            for(int i = 2; i*i <= n; i++){
                if(n % i == 0){
                    if(i % 2 == 1) {
                        winner = winner || isFirstWinner((n/i), 2);
                        if(winner) {
                            dp.put(key, winner);
                            return winner;
                        }
                    }
                    if((n/i) % 2 == 1) {
                        winner = winner || isFirstWinner((i), 2);
                        if(winner) {
                            dp.put(key, winner);
                            return winner;
                        }
                    }
                }
            }
            winner  = winner || isFirstWinner(n - 1, 2);
            if(winner) {
                dp.put(key, winner);
                return winner;
            }
            dp.put(key, winner);
            return winner;
        }else {
            boolean winner = false;
            if(n % 2 == 1) {
                winner = winner || !isFirstWinner(1, 1);
                if(winner){
                    dp.put(key, !winner);
                    return !winner;
                }
            }
            for(int i = 2; i*i <= n; i++){
                if(n % i == 0){
                    if(i % 2 == 1) {
                        winner = winner || !isFirstWinner((n/i), 1);
                        if(winner) {
                            dp.put(key, !winner);
                            return !winner;
                        }
                    }
                    if((n/i) % 2 == 1) {
                        winner = winner || !isFirstWinner((i), 1);
                        if(winner) {
                            dp.put(key, !winner);
                            return !winner;
                        }
                    }
                }
            }
            winner  = winner || !isFirstWinner(n - 1, 1);
            if(winner) {
                dp.put(key, !winner);
                return !winner;
            }
            dp.put(key, !winner);
            return !winner;
        }
    }
    public static void main(String[] args) throws IOException{
        Reader sc = new Reader();
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0){
            int n = sc.nextInt();
            dp = new HashMap<>();
            if(isFirstWinner(n, 1)){
                sb.append("Ashishgup").append("\n");
            }else {
                sb.append("FastestFinger").append("\n");
            }
//            if(n == 1){
//                sb.append("FastestFinger").append("\n");
//                continue;
//            }
//            if(n % 2 == 1){
//                sb.append("Ashishgup").append("\n");
//                continue;
//            }
//            boolean turn = true;
//            while (true){
//                if(n % 2 == 1 && n != 1){
//                    if(turn){
//                        sb.append("Ashishgup").append("\n");
//                        break;
//                    }else {
//                        sb.append("FastestFinger").append("\n");
//                        break;
//                    }
//                }else if(n == 1){
//                    if(turn){
//                        sb.append("FastestFinger").append("\n");
//                        break;
//                    }else{
//                        sb.append("Ashishgup").append("\n");
//                        break;
//                    }
//                }
//                boolean found = false;
//                for(int i = 3; i*i <= n; i+=2){
//                    if(n % i == 0){
//                        found = true;
//                        turn = !turn;
//                        n /= i;
//                        break;
//                    }
//                }
//                if(found) continue;
//                turn = !turn;
//                n--;
//            }
        }
        System.out.print(sb.toString());
    }

    /** Faster input **/
    static class Reader {
        final private int BUFFER_SIZE = 1 << 32;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[1024*16];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();}
    }
}
