Số xâu con tốt

Cho xâu $s$ chỉ gồm các chữ cái Latinh in thường. Với một xâu $t$ khác rỗng, ta gọi tập kí tự của $t$ là tập hợp các kí tự xuất hiện trong $t$. Ví dụ, tập kí tự của xâu aab là $\{a,b\}$.

Xét xâu con $s[a,b]=s_a{s}_{a+1}\dots s_b$ (với $1\le a\le b\le |s|$). Hai xâu con được coi là khác nhau nếu chúng nằm ở hai vị trí khác nhau, kể cả khi nội dung giống hệt.

Cho trước một tập kí tự $C$ khác rỗng. Một xâu con $s[a,b]$ có tập kí tự bằng đúng $C$ được gọi là cực đại theo bao hàm nếu không tồn tại xâu con $s[x,y]$ nào của $s$ thỏa mãn $1\le x\le a$ và $b\le y\le |s|$, $y-x+1>b-a+1$, và tập kí tự của $s[x,y]$ cũng bằng $C$.

Ký hiệu $r(C,s)$ là số lượng xâu con cực đại theo bao hàm có tập kí tự đúng bằng $C$.

Cho xâu $s$ và $m$ tập kí tự $C_1,C_2,\dots ,C_m$ (mỗi tập được mô tả bằng một xâu không có kí tự lặp). Với mỗi $i$, hãy tính $r(C_i,s)$.

Dữ liệu vào

• Dòng đầu chứa xâu $s$ khác rỗng.
• Dòng thứ hai chứa số nguyên $m$.
• Tiếp theo là $m$ dòng, dòng thứ $i$ chứa một xâu $c_i$ gồm các kí tự khác nhau, mô tả tập $C_i$.

Dữ liệu ra

In ra $m$ số nguyên, mỗi số trên một dòng — giá trị $r(C_i,s)$ tương ứng.

Ràng buộc

• $1\le |s|\le {10}^6$
• $1\le m\le {10}^4$
• Mọi kí tự trong các xâu đều là chữ cái Latinh in thường.
• Các kí tự trong mỗi $c_i$ đôi một khác nhau. Các tập $C_i$ không nhất thiết phân biệt.

Ví dụ