2020-10-08

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ashishgup and FastestFinger play a game.

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

Divide nn by any of its odd divisors greater than 11.Subtract 11 from nn if nn is greater than 11.

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 tt (1≤t≤1001≤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  — nn (1≤n≤1091≤n≤109).

Output

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

Example

input

Copy

7 1 2 3 4 5 6 12

output

Copy

FastestFinger Ashishgup Ashishgup FastestFinger Ashishgup FastestFinger Ashishgup

Note

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

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

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

In the last test case, n=12n=12, Ashishgup divides it by 33. Now n=4n=4, FastestFinger is forced to subtract 11, and Ashishgup gets 33, so he wins by dividing it by 33.

解题说明：此题涉及到博弈，找规律能发现，若 n 是奇数，n 除以它本身 ，A 赢。若为偶数，只要有一个因数是奇数，那么一定存在最大的奇因数，除以这个最大的，一定变为偶数，若不为 2 ，对手减一后 ，A 一定赢。

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int k = 0; while (n % 2 == 0) { k++; n = n / 2; } int f = 0; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { f = 1; break; } } if (((n == 1) && (k == 0)) || ((n == 1) && (k > 1)) || ((n > 1) && (f == 0) && (k == 1))) { cout << "FastestFinger" << "\n"; } else { cout << "Ashishgup" << "\n"; } } return 0; }