Ashishgup и FastestFinger играют в игру.
Они начинают с целого числа \(n\) и начинают делать ходы по очереди. На каждом ходу игрок может сделать любой из следующих двух ходов:
- Разделить \(n\) на один из его нечетных делителей, который больше чем \(1\).
- Вычесть \(1\) из \(n\), если \(n\) больше чем \(1\).
Обратите внимание, что множество делителей числа включает само число.
Если игрок не может сделать ход он проигрывает игру.
Ashishgup ходит первым. Определите победителя игры, если оба игрока играют оптимально.
Выходные данные
Для каждого набора входных данных, выведите «Ashishgup», если он побеждает в игре и «FastestFinger» иначе (без кавычек).
Примечание
В первом наборе входных данных \(n = 1\) и Ashishgup не может сделать ход. Он проигрывает.
Во втором наборе входных данных \(n = 2\) и Ashishgup вычитает \(1\) на первом ходу. Теперь \(n = 1\) и FastestFinger не может сделать ход, поэтому он проигрывает.
В третьем наборе входных данных \(n = 3\) и Ashishgup делит на \(3\) на первом ходу. Теперь \(n = 1\) и FastestFinger не может сделать ход, поэтому он проигрывает.
В последнем наборе входных данных \(n = 12\) и Ashishgup делит на \(3\) на первом ходу. Теперь \(n = 4\), FastestFinger может только вычесть \(1\) и Ashishgup получает число \(3\). Наконец, он побеждает после деления этого числа на \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
2
3
4
5
6
12
|
FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup
|