## 题目描述

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.org/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.org/upload/vjudge_pic/CF811E/d3d891fc856386c8b0c1e1a004521369cd8ed774.png)