Title Description
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≤109).
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.
Topic Essentials
Given a positive integer n, there are two operations:
(1) divide n by an odd factor greater than one of n; (2) subtract n by one if n > 1.
Two people play a game. Each person can choose an action at a time. In the end, whoever can't do it loses.Ask who will win.
Topic Analysis
This is a game theory topic with two branches.
1 is a mustfail state, from which one can deduce two mustwin states: 2 and odd (these are the two branches).

2 This branch:
It can be inferred from this branch that 2*a prime number (prime > 2) is a mustfail state.(Dividing the primitive first leaves the opponent with 2 wins; the 1 action leaves the opponent with odd wins)
Thus, it can be inferred that 2*a prime ^n (prime >2) is a mustfail state.(The first hand can be directly divided by the n1 power of this prime number, leaving the opponent 2*a prime number to lose)
Branch 1:1(0) > 2(1) > 2*prime (0) > 2*prime ^n(1)

The odd branch:
From the odd branch, 2^n (n>1) is a mustfail state.(Because 2n can't be divided by odd numbers, you can only choose 1 and it becomes odd)
It can then be inferred that an odd number of 2^n* is a winner.(First you can divide your hand directly by this odd number, and then you leave the other party with a 2N losing streak)
Branch 2:1(0) >Odd (1) > 2^n(0) > 2^n*Odd (1)
The code is as follows
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <stack> #include <map> #include <unordered_map> #include <queue> #include <vector> #include <set> #include <algorithm> #include <iomanip> #define LL long long using namespace std; const int N=2e3+5; bool is_prime(int x) { for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true; } int main() { int t; cin>>t; while(t) { int n; cin>>n; if(n==1) {puts("FastestFinger"); continue;} if(n&1n==2) {puts("Ashishgup"); continue;} bool flag; if(n%4==0) //Branch 2 { while((n&1)==0) n>>=1; if(n==1) flag=false; else flag=true; } else //Branch 1 { n>>=1; if(is_prime(n)) flag=false; else flag=true; } if(flag) puts("Ashishgup"); else puts("FastestFinger"); } return 0; }