Kitty and Katty

Kitty and Katty play a game starting with N stones. On each turn, a player can remove either 1 or 2 stones from the pile. The player who takes the last stone wins. Both play optimally. Determine the winner: return 1 if Kitty (first player) wins, 2 if Katty (second player) wins.

Examples
Input: 4
Output: 1
Hints

Kitty and Katty

Kitty and Katty play a game starting with N stones. On each turn, a player can remove either 1 or 2 stones from the pile. The player who takes the last stone wins. Both play optimally. Determine the winner: return 1 if Kitty (first player) wins, 2 if Katty (second player) wins.