Avtomatik Ticarət

Bir broker şirkəti avtomatik ticarəti aşkar etmək istəyir. Onlar düşünürlər ki, müəyyən bir alqoritm özünü təkrarlayır; yəni, müəyyən bir müddət sonra eyni ticarət ardıcıllığını təkrarlayır. Şirkət, birlikdə ticarət edilməsi ehtimalı olan 26 əsas səhm dəstini müəyyən edib və ticarət ardıcıllığını hərflərlə kodlaşdırıb: hər bir hərf müəyyən bir səhmi təmsil edir, böyük hərf alış, kiçik hərf isə satış deməkdir. Onlar istəyirlər ki, siz bir proqram yazasınız və bu proqram hər hansı iki başlanğıc nöqtəsi üçün, həmin iki nöqtədən başlayaraq, eyni ticarət ardıcıllığının ən uzununu müəyyən etsin.

Giriş verilənləri

Girişdə bir neçə test halı olacaq. Hər test halı birinci sətirdə yalnız böyük və kiçik hərflərdən ibarət olan bir s sətiri ilə başlayacaq (1 ≤ length(s) ≤ 100000). Növbəti sətirdə q tam ədədi olacaq (1 ≤ q ≤ 100000), bu da sorğuların sayını göstərir. Sonrakı q sətir hər bir sorğunu iki tam ədəd, i və j (0 ≤ i < j < length(s)) ilə təsvir edir, bu da sətirdəki sıfırdan başlayan iki mövqeni təmsil edir. Giriş yalnız ulduz ('*') olan bir sətirlə bitəcək.

Çıxış verilənləri

Hər bir sorğu üçün, i nöqtəsindən başlayaraq j nöqtəsindən başlayan ticarət ardıcıllığı ilə eyni olan ən uzun ardıcıllığın uzunluğunu göstərən bir tam ədəd çıxarın. Boşluq çıxarmayın. Çıxış sətirləri arasında boş sətir çap etməyin.