trokut — COCI CONTEST_#5
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 24
Algorithms: game theory, number theory

### Croatian Open Competition in Informatics
### Round 5, March 16th 2024

# Task Trokut

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

She drew *N* points on paper so that they form the vertices of a regular *N*-gon and labeled them sequentially from 1 to *N*. The player whose turn it is selects two of the drawn *N* points such that the line segment connecting those two points does not intersect any of the previously drawn line segments and connects those two
![alt_text](_page_0_Picture_5.jpeg)
points. Line segments are **allowed** to touch at vertices. A player wins if after their move there exist three connected line segments forming a triangle, i.e., if there exist three points such that they are all connected by the drawn line segments. Of course, players are allowed to connect adjacent vertices, and those line segments are considered for triangle formation. Players take turns, and Lucija is the first to play.

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

## Input

In the first row there is an integer *T* (1 ≤ *T* ≤ 10 000), number of scenarios. In the next *T* rows there is an integer *N* (3 ≤ *N* ≤ 10^9), number of points Lucija drew on a piece of paper.

## Output

In *T* rows, for every scenario in given order, output "Ivan" or "Lucija" (without quotes), winner in a given scenario.

## Scoring

| Subtask | Points | Constraints                |
|---------|--------|----------------------------|
| 1       | 13     | $T \le 18, N \le 20$       |
| 2       | 36     | $T \le 998, N \le 1000$    |
| 3       | 15     | $N \le 10^5$               |
| 4       | 46     | No additional constraints. |

## Examples

| Input | Input |
|-------|-------|
| 3     | 3     |
| 3     | 7     |
| 4     | 8     |
| 5     | 9     |
| Output| Output|
| Lucija| Lucija|
| Lucija| Lucija|
| Ivan  | Ivan  |

## Clarification of the first example:

![alt_text](_page_1_Picture_0.jpeg)

When *N* = 3, then all three possible line segments must be connected, and Lucija wins. When *N* = 4, then Lucija can connect the line segment between points 1 and 3. We see that after any move by Ivan, Lucija can connect a triangle and win.

Starter code: