В свободное время Владик оценивает красоту флагов.
Флаг можно представить как матрицу n × m из целых положительных чисел.
Определим красоту матрицы, как количество пятен в ней. Пятном назовем некоторое множество клеток с одинаковыми числами таких, что между любой парой клеток множества существует путь по смежным по стороне клеткам. Пример разделения матрицы на пятна:
Но в этот раз он решил что-то поменять и начать оценивать не весь флаг целиком, а только некоторый его отрезок. Отрезок флага можно описать как подматрицу матрицы флага с противоложными углами в (1, l) и (n, r), где 1 ≤ l ≤ r ≤ m.
Помогите Владику посчитать красоту для некоторых отрезков флага!
Выходные данные
Для каждого отрезка в отдельной строке выведите количество пятен на нем.
Примечание
Разделение на пятна для каждого отрезка:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|