# Ninja Fight

Easy
0/40
Average time to solve is 10m
Contributed by

## Problem statement

Two Ninjas, “Ninja 1” and “Ninja 2”, are here to fight and they want to prove themselves stronger than the other, and to prove so they decided to play a game and whosoever will be the winner of the game will be stronger than the other.

The Game is, given an integer 'N' at the start, the Ninja in his turn has to select a positive integer x such that 'N' is divisible by x ('N' % x = 0) and subtract x from 'N'. The game stops when 'N' becomes 1, now if both the Ninjas alternate their turns starting from “Ninja 1”, your task is to determine the winner if both the Ninjas play optimally.

The player who makes the last move is the winner i.e. The player who is unable to make the move is the loser.

Note:
``````x should never be equal to the current value of 'N'.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10^5
1 <= N <= 10^9

Time limit: 1 sec
``````
##### Sample Input 1:
``````2
9
2
``````
##### Sample Output 1:
``````2
1
``````
##### Explanation for Sample Output 1:
``````In test case 1,

'N' = 9
Ninja 1 subtracts 3, Now 'N' = 6
Ninja 2 subtracts 1, Now 'N' = 5
Ninja 1 subtracts 1, Now 'N' = 4
Ninja 2 subtracts 1, Now 'N' = 3
Ninja 1 subtracts 1, Now 'N' = 2
Ninja 2 subtracts and Now 'N' = 1.

Hence Ninja 2 is the winner.

In test case 2,

'N' = 2
Ninja 1 subtracts 1, which makes 'N' = 1 and no steps for Ninja 2 to play.

Hence, Ninja 1 is the winner.
``````
##### Sample Input 2:
``````2
1
4
``````
##### Sample Output 2:
``````2
1
``````
##### Explanation for Sample Output 2:
``````In test case 1,

'N' = 1 and thus Ninja 1 cannot play any turn and hence Ninja 2 is the winner.

In test case 2,

'N' = 4
Ninja 1 subtracts 1(plays optimally), Now 'N' = 3
Ninja 2 has no other choice rather than to subtract 1, Now 'N' = 2
Ninja 1 subtracts 1 and now 'N' = 1.

Hence, Ninja 1 is the Winner.
``````
Console