# 651 (Div. 2)C. Number Game (Game Theory, Thinking)

#### 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 must-fail state, from which one can deduce two must-win states: 2 and odd (these are the two branches).

1. 2 This branch:
It can be inferred from this branch that 2*a prime number (prime > 2) is a must-fail 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 must-fail state.(The first hand can be directly divided by the n-1 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)

2. The odd branch:
From the odd branch, 2^n (n>1) is a must-fail 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 2-N 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&1||n==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;
}
``````

Added by jb489 on Wed, 24 Jun 2020 03:56:27 +0300