codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.