Masala #0526

Sizga \(s\) va \(t\) satrlar berilgan bo’lib, \(s\) satr ichidan \(t\) satrni qidirishingiz talab etiladi. \(t\) satr \(?\) belgisi va lotin alifbosining kichik harflaridan tashkil topgan. \(?\) belgisi bu lotin alifbosinng kichik harflaridan istalgan biri deb qarash mumkun. Sizning vazifangiz \(s\) satr ichidan mumkun bo’lgan holatlarda qancha \(t\) satrni qirqib olish mumkin, agar qirqib olishning imkoni bo’lsa, har bir qirqib olish mumkin bo’lgan \(s[i,…j] (i\leq j)\) satrning i-chi indeksini topish talab etiladi.

Kirish fayilining dastlabki satrida \(q (1\leq q\leq 100)\) testlar soni. Keyingi \(2q\) ta satirda mos ravishda \(s\) va \(t\) lar kiritiladi \(s\),\(t\)\((1\leq |s|\leq 50000, 1\leq |t|\leq 100)\). Kiruvchi ma’lumotlarda \(s\) faqatgina lotin alifbosining kichik harflaridan, \(t\) esa lotin alifbosining kichik harflari va \(?\) belgisidan tashkil topgan.  

Jami \(q\) ta testga javobni chiqaring. \(s\) satr ichidan \(t\) satrni jami nechi xil usulda qirqib olish mumkinligi va keyingi satrda qirqib olish nechinchi indeksdan boshlanishini chop eting, agar birorta ham mavjud bo’lmasa mos ravishda 0 va bo’sh joyni chop eting.