Agenti jedne tajne obavještajne agencije komuniciraju uz pomoć tajnih šifri, koje su s vremenom naučili jako brzo čitati i pisati. Svaka riječ je niz znakova sastavljenih isključivo do velikih slova engleske abecede. Međutim, u agenciju je došao novi tajni agent, koji se još uvijek nije navikao na šifrirane poruke i treba mu pomoć prilikom dešifriranja poruka. Dešifriranje poruka funkcionira na način da se neko slovo zamjeni nizom znakova. Agenti znaju koja slova se mogu zamjeniti kojim nizovima, a prilikom dešifriranja uzmu originalnu riječ i umjesto slova, koja se mogu zamjeniti, unutar riječi umetnu novi niz. Takva zamjena se naziva produkcijom. Primjenom svih mogućih produkcija na početni niz znakova agenti dobiju novu dešifriranu i proširenu riječ. Da bi novom agentu olakšali rad, napišite program koji računa dužinu nove riječi. Ulaz U prvom retku se nalazi jedna riječ, sastavljena isključivo od velikih slova engleske abecede. Riječ će biti duga najviše 1000 znakova. U drugom retku se nalazi jedan prirodan broj N (1 ≤ N ≤ 26), koji predstavlja broj produkcija. U svakom od sljedećih N redaka nalaze se po jedan znak Ci i jedan niz znakova Si , koji predstavljaju i-tu produkcija u kojoj se znak Ci zamjenjuje nizom znakova Si . Znak Ci i niz znakova Si će biti sastavljeni od velikih slova engleske abecede, a Si će biti dužine između 1 i 50 znakova (uključivo). NAPOMENA: Neće se pojaviti dvije produkcije koje mjenjaju isto slovo. Izlaz U prvi i jedini redak potrebno je ispisati dužinu nove proširene riječi