Round and Round We Go

Time limit1sMemory limit128 MB

Summary

For each given number, decide whether every product by 1 through its digit count is a rotation of its digits, keeping leading zeros.

Level: Medium6 of 10
Topics: String, Math, Implementation, Brute force
Solved: No attempts yet

Problem

A cyclic number is an integer with $n$ digits that, when multiplied by every integer from $1$ to $n$ , produces a cyclic permutation (a “rotation”) of its own digits. Picture the digits laid out on a circle so that the position after the last digit wraps around to the first: each product then uses exactly the same digits in the same circular order, though it may start at a different position.

For example, $142857$ is cyclic, as the following table shows:

142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

Write a program that decides, for each given number, whether or not it is cyclic.

Input

The input is a list of integers, one per line, each from $2$ to $60$ digits long. Leading zeros are significant: they are part of the number and count toward $n$ . So 01 is a two-digit number, different from the one-digit number 1. Read until the end of input.

Output

For each input integer, print one line. Reproduce the number exactly as it appeared in the input (keeping any leading zeros), followed by is cyclic when it is a cyclic number and is not cyclic otherwise.

Examples3

Example 1

Input

142857
142856
142858
01
0588235294117647

Expected output

142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

Example 2
Input
```
142857
```
Expected output
```
142857 is cyclic
```
Example 3
Input
```
285714
```
Expected output
```
285714 is not cyclic
```