Бесі нещодавно отримала набір фарб. Полотно може бути представлене як \(N \times M\) прямокутник із комірок, де рядки пронумеровані \(1\ldots N\) зверху вниз, а стовпці пронумеровані \(1\ldots M\) зліва направо (\(1\le N,M\le 1000\)).

Пофарбована комірка представляється великою літерою від 'A' до 'Z'. Спочатку всі комірки не розфарбовані, і комірка не може фарбуватися більше одного разу.

У Бесі є бажаний колір для кожної комірки. Вона може фарбувати безліч комірок одним дотиком, якщо ця безліч утворює зв'язну компоненту, тобто будь-яка її комірка досяжна з будь-якої іншої через послідовність сусідніх комірок. Дві комірки називаються сусідніми, якщо вони мають спільну сторону.

Наприклад, розглянемо полотно \(3\times 3\)

AAB
BBA
BBB

Воно може бути розфарбоване за 4 торкання так:

... ..B AAB AAB AAB
... -> ... -> ... -> BB. -> BBA
... ... ... BBB BBB

Неможливо розфарбувати його менш ніж за 4 дотики.

Будучи авангардисткою, Бесі має намір пофарбувати лише підрегіон полотна. Зараз вона розглядає \(Q\) кандидатів (\(1\le Q\le 1000\)), кожен з яких представляється чотирма цілими числами \(x_1\), \(y_1\), \(x_2\), \(y_2.\) Це означає, що підпрямокутник складається з усіх комірок з рядками в діапазоні від \(x_1\) до \(x_2\) включно, і колонками в діапазоні від \(y_1\) до \(y_2\) включно.

Для кожного такого прямокутника, яка потрібна мінімальна кількість дотиків, щоб розфарбувати кожну з комірок цього прямокутника бажаним кольором, залишаючи не зафарбованими всі комірки поза цим підпрямокутником. Зауважимо, Бесі нічого не фарбує реально, тому відповіді для кожного кандидата є незалежними.

Зауваження: Час на тест у цій задачі є на 50% вище ніж за умовчанням, а обмеження оп пам'яті 512 Мбт - удвічі більше ніж за замовчуванням.

Формат вхідних даних

Перший рядок введення містить \(N\), \(M\), \(Q\).

Кожен з наступних \(N\) рядків містить рядок з \(M\) великих літер, які представляють бажаний колір кожного рядка полотна.

Кожен із наступних \(Q\) рядків містить чотири розділені одиночними пробілами цілих числа \(x_1,y_1,x_2,y_2\), що представляють підпрямокутник (\(1\le x_1\le x_2\le N\), \(1\le y_1\le y_2\le M\)).

Формат вихідних даних

Для кожного з \(Q\) запитів виведіть відповідь в окремому рядку.

Приклад вхідних даних

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

Приклад вихідних даних

6
3
2
1
4
1
3
2
2

Перший кандидат – на все полотно, його можна розфарбувати за 6 дотиків.

Другий кандидат - підпрямокутник із бажаними кольорами

ABBA

і може бути розфарбований за 3 торкання. Зауважимо, що хоча комірки \((3,5)\) і \((3,8)\) можуть бути розфарбовані в колір \(A\) одним дотиком на цілому полотні, вони не можуть бути так розфарбовані у прямокутнику.

ОЦІНЮВАННЯ:

• У тестах 1-2 \(N,M\le 50\).
• У тестах 3-5, Полотно не містить цикл одного кольору. Тобто немає послідовності різних комірок \(c_1,c_2,c_3,\ldots,c_k\) таких, що виконуються такі обмеження:
  • \(k>2\)
  • Всі \(c_1,\ldots,c_k\) мають один і той же бажаний колір.
  • \(c_i\) сусідня з \(c_{i+1}\) для кожного \(i\)? \(1\le i<k\).
  • \(c_k\) сусідня c_1~.

  Зауважимо, що \(3\times 3\) містить цикл одного кольору - чотири B у лівому нижньому кутку </li>

• У тестах 6-8, кожна зв'язна компонента складається з комірок одного бажаного кольору, може розглядатися як квадрат 2 на 2 зі сторонами паралельними осям координат. Квадрат \(3\times 3\) полотна вище не задовольняє цю властивість. (зв'язна компонента з 5 B не може утримуватися у квадраті 2 на 2.
• У тестах 9-11, кожна зв'язна компонента, що складається з комірок одного кольору міститься в квадраті 3 на 3 зі сторонами паралельними осям координат. Полотно \(3\times 3\) вище задовольняє цю властивість.
• У тестах 12-20 немає додаткових обмежень.