Binər ağac
Binari ağac - hər bir düyünün ən çox iki uşağı olan, sol və sağ uşaq olan ağacvari məlumat strukturu. Uşaqları olan düyün həmin uşaqların valideyni adlanır.
Təlimatlarla olan sətir L, R və U hərflərindən ibarətdir. L Sol, R Sağ, U isə Yuxarı deməkdir. Onların mənaları aşağıda izah olunacaq.
Bir dəfə mən sonsuz böyük bir binari ağac çəkdim. Bu ağacda hər bir zirvənin dəqiq iki uşağı (sol və sağ uşaq) var idi, hər biri ataya malik idi. Bu məsələdə kökün atasını kökün özü hesab edəcəyik. Mən qələmi kökə qoyuram və təlimatlar sətiri S ilə hərəkət edirəm. Yəni, onun ilk simvoluna baxırıq və əgər o L bərabərdirsə, sol oğula gedirik, əgər o R bərabərdirsə, sağ oğula gedirik, əgər o U bərabərdirsə, ata tərəfə gedirik. Əgər kökdən U əmri gəlirsə, kökdə qalırıq, çünki kökün atası özüdür.
Başqa bir təlimatlar sətiri T olsun. S təlimatlar sətirini yerinə yetirdikdən sonra dayandığımız zirvədən başlayaraq T sətirinin əmrlərini yerinə yetirəcəyik. Lakin indi T sətirindən istənilən sayda təlimatı (hətta hamısını) ötürə bilərik. T əmrlərini yerinə yetirərək (və onları istənilən qaydada ötürərək) neçə fərqli zirvəyə çata biləcəyimizi müəyyən etmək lazımdır.
Məsələn:
S = L və T = LU olsun. Cavab 3-ə bərabərdir. S işlədikdən sonra kökün sol oğlunda dayanırıq. T təlimatlarını 4 variantda işlətmək olar:
Bütün hərfləri ötürmək: eyni zirvədə qalırıq.
L-i ötürüb U-nu yerinə yetirmək: kökə qayıdırıq.
L-i yerinə yetirib U-nu ötürmək: cari zirvənin sol oğluna keçirik.
L və U-nu yerinə yetirmək: eyni zirvədə qalırıq, 1 halında olduğu kimi.
T yerinə yetirildikdən sonra 3 fərqli zirvəyə çata bildiyimiz üçün cavab 3-ə bərabərdir.
Giriş verilənləri
Birinci sətir testlərin sayı n (n ≤ 15) verir. Hər bir test iki boş olmayan sətirdən ibarətdir. Birinci sətir təlimatlar dəsti S, ikinci isə təlimatlar dəsti T verir. Sətirlər L, R və U hərflərindən başqa heç bir hərf ehtiva etmir. Sətirlərin uzunluğu 100000-dən çox deyil.
Çıxış verilənləri
Hər bir test üçün onun nömrəsini və çata bilən zirvələrin sayını çıxarın. Cavab böyük ola biləcəyi üçün onu 21092013 modulu ilə çıxarın.