Qurdlar
Bioloqlar maraqlı bir qurd növünü araşdırırlar. Hər bir qurd müxtəlif növ hüceyrələrdən ibarət bir sıra şəklində təsvir edilə bilər. Qurd doğulduqda, yalnız bir hüceyrədən ibarət olur. Hər gün, qurdun yalnız 1 hüceyrəsi böyüyərək 2 hüceyrəyə çevrilir. Belə bir qurdun yaşını müəyyən etmək asandır, çünki bu, qurdun hüceyrələrinin sayından bir az fərqlidir.
Qurdun böyüməsi zamanı bir hüceyrə təsadüfi 2 hüceyrəyə çevrilmir; hər bir qurdun öz "böyümə qaydaları" dəsti var (DNT-sində kodlanmış). Böyümə qaydası A => BC kimi ifadə edilir, burada A, B və C böyük hərflərdir (A-T hərfləri ilə), qurdun hüceyrələrinin müxtəlif növlərini təmsil edir. A => BC qaydası bir gün ərzində tək bir A hüceyrəsinin ardıcıl olaraq BC olan 2 bitişik hüceyrəyə çevrilə biləcəyini bildirir. Qeyd edək ki, I => JK qaydası I => KJ qaydasından fərqlidir. Müxtəlif qurdlar fərqli böyümə qaydaları dəstinə malik ola bilər.
Qurdlar indi alimləri çaşdırıblar. Naməlum səbəbdən bəzi qurdlar yeni bir növə mutasiya ediblər. Bu yeni qurd növü eyni xüsusiyyətlərə malikdir, lakin böyüməsi zamanı bədəninin bir neçə hissəsi eyni vaxtda böyüyə bilər. Yəni, hər gün onun istənilən (ən azı bir, ən çoxu bütün) hüceyrələri böyüyə bilər; böyüyən hər bir hüceyrə dəqiq 2 hüceyrəyə çevriləcək (böyümə qaydalarına uyğun olaraq).
Mutasiya nəticəsində qurdun yaşını müəyyən etmək artıq asan deyil. Əslində, bəzi qurdların dəqiq yaşı müəyyən edilə bilməz. Sadə bir nümunə olaraq, əgər bir qurdun böyümə qaydaları: A => BC, B => AC, C => AB və qurdun cari hüceyrə quruluşu ACAB olarsa, qurd ya 2, ya da 3 günlük ola bilər (A => BC => ACAB, və ya A => BC => ACC => ACAB). Sizin vəzifəniz hər hansı bir mutasiya olunmuş qurdun mümkün olan ən gənc yaşını tapmaqdır.
Giriş verilənləri
Girişdə müayinə üçün bir neçə qurd olacaq. Hər bir qurdun məlumat dəsti N (1 <= N <= 80) tam ədədi ilə başlayır, böyümə qaydalarının sayı. Növbəti N sətir hər biri cari qurd üçün böyümə qaydasını təmsil edən 3 böyük hərf (hərflər A-T ilə) ehtiva edir. 1-ci hüceyrə böyümə prosesində ardıcıl olaraq 2-ci və 3-cü hüceyrələrə çevrilə bilər (və əvəz edilə bilər). Yəni, sətir:
ABC
cari qurd üçün A => BC böyümə qaydası deməkdir.
Hər bir qurdun məlumat dəstinin növbəti (və son) sətri böyük hərflərdən ibarət bir sətir ehtiva edir (hərflər A-T ilə). Bu sətir qurdun cari hüceyrə quruluşunu təmsil edir. Girişdəki hər bir qurdun ən azı 1 və ən çox 50 hüceyrəsi olacaq.
Son qurd bir 0 tək sətir ilə izlənəcək.
Çıxış verilənləri
Hər bir qurd üçün, əgər qurd verilmiş böyümə qaydaları dəsti ilə (istənilən təsadüfi tək hüceyrədən başlayaraq) verilmiş hüceyrə ardıcıllığına qədər böyüyə bilərsə, onda qurdun minimum yaşını, günlərdə, öz sətirində tam ədəd kimi çap edin. Əgər qurd verilmiş qaydalar dəsti ilə (istənilən təsadüfi tək hüceyrədən başlayaraq) verilmiş hüceyrə ardıcıllığına qədər böyüyə bilməzsə, onda sadəcə '-1' nömrəsini öz sətirində çap edin. Çıxışlar arasında boş sətirlər çap etməyin.