SPOJ in Gyumri

Դուք երևի ծանոթ եք Տրիբոնաչիի հաջորդականությանը, որը սահմանվում է հետևյալ կերպ.

a₀=0, a₁=0, a₂=1, a_i=a_i-3+a_i-2+a_i-1, երբ i≥3:

Օգտվելով Տրիբոնաչիի թվերից` տրված m բնական թվի համար սահմանենք հետևյալ հաջորդականությունը.

b₀=a₀ mod m, b₁=a₁ mod m, . . . , b_i=a_i mod m, . . . , (մնացորդ ըստ մոդուլ m-ի):

Գրե՛ք ծրագիր, որը կորոշի {b_i} հաջորդականության տարրերի կրկնման պարբերության երկարությունը: Այսինքն, որոշե՛ք այն k թիվը, որի համար

b_k=b₀, b_k+1=b₁, b_k+2=b₂, b_k+3=b₃, . . . :

Մուտքային տվյալներ

Մուտքում տրված է m բնական թիվը (2≤m≤1000):

Ելքային տվյալներ

Ելքում պետք է արտածել {b_i} հաջորդականության տարրերի կրկնման պարբերության երկարությունը: Եթե այդպիսի k գոյություն չունի, ապա արտածել No Solution:

Օրինակներ

Ծանոթություն: Առաջին օրինակում, ունենք.

{a_i} - 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, . . . :

{b_i} - 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, . . . , հետևաբար k=4 (կրկնվում է՝ 0, 0, 1, 1 ենթահաջորդականությունը):