1370C.md (1674B)
1 Source: https://codeforces.com/problemset/problem/1370/C 2 3 C. Number Game 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Ashishgup and FastestFinger play a game. 22 23 They start with a number $n$ and play in turns. In each turn, a player can make any one of the following moves: 24 25 * Divide $n$ by any of its odd divisors greater than $1$. 26 * Subtract $1$ from $n$ if $n$ is greater than $1$. 27 28 Divisors of a number include the number itself. 29 30 The player who is unable to make a move loses the game. 31 32 Ashishgup moves first. Determine the winner of the game if both of them play optimally. 33 34 Input 35 36 The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows. 37 38 The only line of each test case contains a single integer — $n$ ($1 \leq n \leq 10^9$). 39 40 Output 41 42 For each test case, print "Ashishgup" if he wins, and "FastestFinger" otherwise (without quotes). 43 44 Example 45 46 Input 47 48 ``` 49 7 50 1 51 2 52 3 53 4 54 5 55 6 56 12 57 ``` 58 59 Output 60 61 ``` 62 FastestFinger 63 Ashishgup 64 Ashishgup 65 FastestFinger 66 Ashishgup 67 FastestFinger 68 Ashishgup 69 ``` 70 71 Note 72 73 In the first test case, $n = 1$, Ashishgup cannot make a move. He loses. 74 75 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. 76 77 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. 78 79 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$.