# Vladik and Entertaining Flags

## 题意翻译

在一个 n*m 的网格上每个格子都有颜色，q 次询问，每次询问只保留 l 至 r 列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。

## 题目描述

In his spare time Vladik estimates beauty of the flags.
Every flag could be represented as the matrix $ n×m $ which consists of positive integers.
Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF811E/9c3d5d03c8614a33f231cd8f8efd0e706383885b.png)But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at $ (1,l) $ and $ (n,r) $ , where conditions $ 1<=l<=r<=m $ are satisfied.
Help Vladik to calculate the beauty for some segments of the given flag.

## 输入输出格式

### 输入格式

First line contains three space-separated integers $ n $ , $ m $ , $ q $ ( $ 1<=n<=10 $ , $ 1<=m,q<=10^{5} $ ) — dimensions of flag matrix and number of segments respectively.
Each of next $ n $ lines contains $ m $ space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding $ 10^{6} $ .
Each of next $ q $ lines contains two space-separated integers $ l $ , $ r $ ( $ 1<=l<=r<=m $ ) — borders of segment which beauty Vladik wants to know.

### 输出格式

For each segment print the result on the corresponding line.

## 输入输出样例

### 输入样例 #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
```

### 输出样例 #1

```
6
7
3
4
```

## 说明

Partitioning on components for every segment from first test case:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF811E/d3d891fc856386c8b0c1e1a004521369cd8ed774.png)