Bessie קיבלה לאחרונה ערכת ציור, והיא רוצה לצבוע את הגדר הארוכה באחד מקצות המרעה שלה. הגדר מורכבת מ־$N$ קטעים רצופים באורך מטר אחד ($1\le N\le 10^5$). לרשות Bessie עומדים 26 צבעים שונים, המסומנים באותיות 'A' עד 'Z' בסדר עולה של כהות ('A' בהיר מאוד, ו־'Z' כהה מאוד). לכן היא יכולה לתאר את הצבע הרצוי לכל קטע באמצעות מחרוזת באורך $N$ שכל תו בה הוא אות.

בתחילה כל קטעי הגדר אינם צבועים. Bessie יכולה לצבוע כל טווח רציף של קטעים בצבע אחד במשיכת מכחול אחת, כל עוד היא לעולם אינה צובעת צבע בהיר יותר על גבי צבע כהה יותר (אפשר לצבוע רק צבעים כהים יותר על גבי צבעים בהירים יותר).

למשל, קטע לא צבוע באורך ארבע יכול להיצבע כך:

.... -> BBB. -> BBLL -> BQQL

כשזמנה הולך ואוזל, Bessie חושבת שאולי תצטרך להשאיר טווח רציף כלשהו של קטעי גדר לא צבוע! כרגע היא בוחנת $Q$ טווחים מועמדים ($1\le Q\le 10^5$), שכל אחד מתואר על ידי שני מספרים שלמים $(a,b)$ עם $1 \leq a \leq b \leq N$, המציינים את אינדקסי הקצוות של הטווח $a \ldots b$ שיש להשאיר לא צבוע.

לכל טווח מועמד, מהו המספר המינימלי של משיכות מכחול הנדרש כדי לצבוע כל קטע מחוץ לטווח בצבע הרצוי שלו, תוך השארת כל הקטעים שבתוך הטווח לא צבועים? שימו לב ש־Bessie אינה מבצעת צביעה בפועל במהלך התהליך, ולכן התשובות לכל טווח מועמד אינן תלויות זו בזו.

קלט

השורה הראשונה מכילה את $N$ ואת $Q$.

השורה הבאה מכילה מחרוזת באורך $N$ המתארת את הצבע הרצוי של כל קטע גדר.

כל אחת מ־$Q$ השורות הבאות מכילה שני מספרים שלמים $a$ ו־$b$ המופרדים ברווח, המציינים טווח מועמד שייתכן שיישאר לא צבוע.

פלט

עבור כל אחד מ־$Q$ המועמדים, הדפיסו את התשובה בשורה חדשה.

דוגמאות

קלט 1

8 2
ABBAABCB
3 6
1 4

פלט 1

4
3

הערה

בדוגמה זו, החרגת תת־הטווח המתאים לתבנית הרצויה $\texttt{BAAB}$ מצריכה ארבע משיכות מכחול לצביעה, ואילו החרגת $\texttt{ABBA}$ מצריכה רק שלוש.

.... -> AA.. -> ABBB -> ABCB

תתי־משימות

• מקרי הבדיקה 1–4 מקיימים $N,Q\le 100$.
• מקרי הבדיקה 5–7 מקיימים $N,Q\le 5000$.
• למקרי הבדיקה 8–13 אין מגבלות נוספות.

מחברי הבעיה: Andi Qu ו־Brian Dean