Queens on a Torus

Time limit1sMemory limit128 MB

Summary

Decide for each N whether N queens fit on an N by N torus board without sharing a wrapping row, column or diagonal.

Level: Medium7 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Young math students need games too, so someone had to invent a few clever ones for them. One of those games is the queens game.

The board is an $N \times N$ torus: an $N \times N$ square grid whose left edge is glued to its right edge, and whose top edge is glued to its bottom edge.

A queen attacks every square that shares her row, her column, or one of her diagonals. Since opposite edges of the board are glued together, rows, columns and diagonals wrap around the board.

Decide whether $N$ queens can be placed on this board so that no two of them attack each other.

Input

The input has several lines. Each line holds one board size $N$ ( $1 \le N \le 1\,500\,000\,000$ ).

The last line holds 0. Do not process that line.

Output

For every line except the final 0, print one line: Kralovny lze umistit. if the queens fit, or Kralovny se nevejdou. if they do not.

Examples1

Example 1

Input

3
5
0

Expected output

Kralovny se nevejdou.
Kralovny lze umistit.