AB-poemalar

Müasir rekursiv AB-şeir, verilmiş W misrası və iki P[a] və P[b] ifadəsindən yaradılır. Bunların hər biri {a, b} əlifbasında sözlərdir. Şeirin ilk misrası W[1] = W olaraq verilir və n-ci misra, (n - 1)-ci misradakı hər bir a-nı P[a] ifadəsi ilə, hər bir b-ni isə P[b] ifadəsi ilə əvəz etməklə əldə edilir.

Siz hər il bir misra oxumaqla illik AB-şeir oxunuşunu təşkil edirsiniz. Gələcəkdə misraların oxunma vaxtının necə dəyişəcəyini qiymətləndirin. Başqa sözlə, sərhədi tapın:

burada |W[n]| n-ci misradakı hərflərin ümumi sayını göstərir.

Giriş məlumatları

Birinci sətir testlərin sayı t-ni ehtiva edir. Hər bir test üç sətirdən ibarətdir, hər biri {a, b} əlifbasında bir söz ehtiva edir. Bu sözlər müvafiq olaraq P[a], P[b] və W-dir. Sözlər boş deyil və maksimum 1000 simvol ehtiva edir.

Çıxış məlumatları

Hər bir test üçün ayrıca sətirdə bir real ədəd çıxarın: proqram tərəfindən hesablanmış sərhəd. Hesablamada 10^(-9) dəqiqlik səhvinə icazə verilir. Əgər sərhəd mövcud deyilsə, bir mənfi işarə (-) çıxarın.