Background

Translated from COCI 2023/2024 Contest #5 Task 5「Trokut」

Problem Description

Ivan and Lucija are on a long journey far away. They know the trip will last a long time, and at some point they will get bored. While thinking about what to do, Lucija came up with a game.

She draws $N$ points on a sheet of paper so that they form the vertices of a regular $N$-gon, and labels them in order from $1$ to $N$. On a player’s turn, they choose two points such that the line segment connecting them does not intersect any previously drawn segment, and then draw that segment. Segments are allowed to touch at vertices. If after a player’s move there exist three drawn segments that form a triangle, that is, there exist three points such that every pair of them is connected by a drawn segment, then that player wins. Of course, a player may connect adjacent vertices as well, and those segments can also be used to form a triangle. The players alternate turns, and Lucija goes first.

Both players are very skilled, and we assume they play optimally. Your task is to determine, for a given $N$, who will win the game. It can be proven that the game will end after a finite number of moves, and there will always be a winner.

Input Format

The first line contains an integer $T\ (1\le T\le 10\ 000)$, the number of scenarios.

The next $T$ lines each contain an integer $N\ (3\le N\le 10^9)$, the number of points Lucija draws on the paper.

Output Format

Output $T$ lines. For each scenario, in the given order, output Ivan or Lucija, indicating the winner of that scenario.

3
3
4
5

Lucija
Lucija
Ivan

3
7
8
9

Lucija
Lucija
Ivan

Hint

Sample Explanation 1

When $N = 3$, all three possible segments must be drawn, and Lucija wins.

When $N = 4$, Lucija can draw the segment between point $1$ and point $3$. We can see that after any move by Ivan, Lucija can complete a triangle and win.

Subtasks

Translated by ChatGPT 5