Cyclic Numbers

Time limit1sMemory limit512 MB

Summary

Given a list of digit strings up to 1000 digits long, the task checks whether each number is cyclic, meaning its multiples by 1 to n are rotations of its digits.

Level: Easy3 of 10
Topics: String, Simulation, Implementation
Solved: No attempts yet

Problem

A cyclic number is a positive integer $n$ digits in length which, when multiplied by any integer from 1 to $n$ , yields a "cycle" of the digits of the original number. That is, if you consider the number after the last digit to "wrap around" back to the first digit, the sequence of digits in both numbers will be the same, though they may start at different positions.

For example, the number 142857 is cyclic:

$142857 \times 1 = 142857$
$142857 \times 2 = 285714$
$142857 \times 3 = 428571$
$142857 \times 4 = 571428$
$142857 \times 5 = 714285$
$142857 \times 6 = 857142$

Write a program that determines whether each number is cyclic.

Input

The input is a list of integers, each with 2 to 1000 digits. Leading zeroes are allowed.

Output

For each integer, display the integer and whether or not it is cyclic.

Examples1

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