Bloodline

*No, we won't be talking the next day \ I ain't got nothin' to say (Hell nah) \ I ain't lookin' for my one true love \ Yeah, that ship sailed away* Shivansh and Tina are playing a game. The players move in alternating turns with Shivansh starting first. They have integers $N$ and $K$. In one move, a player has to: - Choose any non-negative integer $X$ such that $K^X \le N$; - Subtract $K^X$ fro