E. Владик и занимательные флаги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В свободное время Владик оценивает красоту флагов.

Флаг можно представить как матрицу n × m из целых положительных чисел.

Определим красоту матрицы, как количество пятен в ней. Пятном назовем некоторое множество клеток с одинаковыми числами таких, что между любой парой клеток множества существует путь по смежным по стороне клеткам. Пример разделения матрицы на пятна:

Но в этот раз он решил что-то поменять и начать оценивать не весь флаг целиком, а только некоторый его отрезок. Отрезок флага можно описать как подматрицу матрицы флага с противоложными углами в (1, l) и (n, r), где 1 ≤ l ≤ r ≤ m.

Помогите Владику посчитать красоту для некоторых отрезков флага!

Входные данные

В первой строке заданы три целых числа n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — размеры флага и количество отрезков соответственно.

В каждой из следующих n строк записано по m целых чисел — описание флага. Все элементы матрицы являются целыми натуральными числами не превышающими 106.

Следующие q строк будут содержать по два целых числа l, r (1 ≤ l ≤ r ≤ m) — границы отрезка для которого Владик хочет посчитать красоту.

Выходные данные

Для каждого отрезка в отдельной строке выведите количество пятен на нем.

Пример
Входные данные
4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5
Выходные данные
6
7
3
4
Примечание

Разделение на пятна для каждого отрезка: