There is an $n$-dimensional cyclic arena for a robot: each coordinate is a residual modulo $p = 998\,244\,353$. Each cartridge contains a command — a shift vector of $n$ residuals modulo $p$. Applying a cartridge once moves the robot exactly by the vector written in it (each coordinate is taken modulo $p$).

A remote control can hold exactly $n$ cartridges. We call a remote control universal if, using only the cartridges installed in it and applying each of them an arbitrary number of times, the robot can get from any cell of the arena to any other one.

There are $m$ cartridges in the warehouse. The $i$-th cartridge contains the shift vector $v_i$.

There are $q$ independent warehouse inspection reports. In the $j$-th report, only the cartridges with indices from $l_j$ to $r_j$ remain fresh — they can be taken from the warehouse for free, while all other warehouse cartridges have expired and are prohibited from use.

Moreover, within each report, it is allowed to manufacture any number of new fresh cartridges. Each such cartridge costs one coin, and its shift vector can be chosen arbitrarily (including coincident vectors). Manufactured cartridges are not preserved between reports.

For each report, determine the minimum number of coins needed to assemble two universal remote controls from fresh cartridges. Each cartridge can be used at most once and only in one remote control.

Input

The first line contains one integer $1 \le t \le 1000$ — the number of test cases.

For each test case, the first line contains three integers $n$, $m$ and $q$ — the dimension of the arena, the number of cartridges in the warehouse and the number of inspection reports, respectively ($1 \le n \le 150$, $1 \le m, q \le 3 \cdot 10^5$). It is additionally guaranteed that the sum of $n \cdot m$ and the sum of $q$ over all test cases do not exceed $3 \cdot 10^5$.

Then $m$ lines follow, each containing $n$ integers $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$ — the shift vector of the $i$-th cartridge ($0 \le v_{i,k} < p$).

Then $q$ lines follow, each containing two integers $l_j$ and $r_j$ ($1 \le l_j \le r_j \le m$) — in the corresponding inspection report, only the cartridges with indices from $l_j$ to $r_j$ remain fresh.

Output

For each inspection report, output one integer — the minimum number of coins needed to assemble two universal remote controls from fresh cartridges.

Examples

Input 1

1
1 3 4
0
1
2
1 1
2 2
3 3
1 3

Output 1

2
1
1
0

Input 2

1
2 4 3
1 0
0 1
0 1
0 1
1 2
1 3
1 4

Output 2

2
1
1