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.util.*; 
public class Code
{ 
  static List<Pair> prime_factors(int n){
    int p = 0;
    List<Pair> factor =  new ArrayList<>();
    if(n%2 == 0){
      while(n % 2 == 0){
        p++;
        n /=2;
      }
       factor.add(new Pair(2, p));
    }
     double sqr = Math.sqrt(n);
    for(int i=3; i<=sqr; i++){
      if(n % i == 0){
        p = 0;
        while(n % i == 0){
          p++;
          n = n/i;
        }
        factor.add(new Pair(i, p));
      }
    }
    if(n > 1)
      factor.add(new Pair(n,1));
    return factor;
  }
  static boolean fun( int n){
    List<Pair> factor = prime_factors(n);
        int even=0, odd=0, size = factor.size();
        even = factor.get(0).pow;
        for(int i=1; i<size; i++){
          odd += factor.get(i).pow;
        }
        if(even == 1 && odd == 0)
           return true;
        else if(even == 1 && odd == 1)
          return false;
        else if(even == 1 && odd > 1)
          return true;
        if(even >1 && odd == 0)
          return false;
        else 
          return true;

  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
   
    while(t-- > 0)
    {
      int n = sc.nextInt();

          if( n == 1){
            System.out.println("FastestFinger");
            }
          else if( n % 2 == 0){
                  boolean f = fun(n);
                  if(f)
                    System.out.println("Ashishgup");
                 else 
                    System.out.println("FastestFinger");
                   
          }
          else{
           
               System.out.println("Ashishgup");

          }
        }

  }
}
class Pair{
  int n, pow;
  Pair(int n, int pow){
    this.n = n;
    this.pow = pow;
  }

}

