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.
#include <bits/stdc++.h>
using namespace std;
void read() {}
template <class T, class... Arg>
void read(T &x, Arg &&...args) {
  cin >> x;
  read(args...);
}
void print_err() { cerr << "\n"; }
template <class T, class... Arg>
void print_err(T x, Arg &&...args) {
  cerr << x << " ";
  print_err(args...);
}
template <class T>
void print_container(T &cont) {
  for (auto iter : cont) {
    cerr << iter << " ";
  }
  cerr << "\n";
}
template <class T>
void debug_arr(T arr, long long int st, long long int en) {
  for (long long int i = st; i < en; ++i) {
    cerr << arr[i] << " ";
  }
  cerr << endl;
}
template <class T>
void read_arr(T arr, long long int n) {
  for (long long int i = 0; i < n; ++i) {
    cin >> arr[i];
  }
}
template <class T>
void read_c(T &arr, long long int n) {
  for (long long int i = 0; i < n; ++i) {
    cin >> arr[i];
  }
}
void CP() {
  ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
  return;
}
char *stringTOCharArray(string str) {
  long long int n = str.length();
  char *ch = new char[n + 1];
  ;
  strcpy(ch, str.c_str());
  return ch;
}
class Graph {
 public:
  list<long long int> *adj_list;
  long long int v;
  Graph(long long int v) {
    this->v = v;
    adj_list = new list<long long int>[v];
  }
  void add_edge(long long int u, long long int v, bool bidirectional = true) {
    adj_list[u].push_back(v);
    if (bidirectional) {
      adj_list[v].push_back(u);
    }
  }
};
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
long long int countodd = 0, countev = 0;
void counto(long long int n) {
  while (n % 2 == 0) {
    countev++;
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      countodd++;
      n = n / i;
    }
  }
  if (n > 2) countodd++;
}
void solve() {
  long long int n;
  read(n);
  if (n == 1) {
    cout << "FastestFinger\n";
    return;
  }
  if (n == 2) {
    cout << "Ashishgup\n";
    return;
  }
  if ((n & n - 1) == 0) {
    cout << "FastestFinger\n";
    return;
  }
  if (n & 1) {
    cout << "Ashishgup\n";
  } else {
    countev = 0;
    countodd = 0;
    counto(n);
    if (countev > 1) {
      cout << "Ashishgup\n";
    } else if (countev == 1 and countodd == 1) {
      cout << "FastestFinger\n";
    } else {
      cout << "Ashishgup\n";
    }
  }
  return;
}
int main() {
  CP();
  long long int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
