Update appNew update is available. Click here to update.

Ninja Fight

Posted: 16 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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'.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains an integer 'N' as described in the problem statement.
Output Format:
For each test case, return 1, if “Ninja 1”, wins the game, otherwise return 2 if "Ninja 2" wins the game.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function. 
Constraints:
1 <= T <= 10^5
1 <= N <= 10^9

Time limit: 1 sec