You have piles of stones arranged in a row. The -th pile contains stones (where can be ). Among all the stones, exactly one stone is special, and you want to find it. Each time, you can choose a number of stones from a pile to be tested, and the test will tell you whether the special stone is among the chosen ones.The stones you choose must come from one pile.

You want to minimize the number of tests needed to identify the special stone in the worst-case scenario.

There are queries, each giving and . For each query, you need to answer the minimum number of tests required to determine the special stone, given that it is within the piles from to .

Since the value of can be large, it will be represented as a binary string of length in the format of a 01 string. The first character of the string is the most significant bit, and the last character is the least significant bit.

The first line contains three positive integers , , and , representing the length of the sequence, the maximum bit length of , and the number of queries, respectively. 

The next  lines each contain a binary string of length  representing .

The next  lines each contain two integers  and , representing the range for the query.

For each query, output the minimum number of tests required to determine the special stone.

5 3 5
100
100
101
001
111
1 3
1 3
3 3
4 4
5 5

4
4
3
0
3

15 8 10
01100110
10101011
01011110
10011100
10100101
01101010
11001010
01000110
11001101
01100011
01100101
10110010
01011101
01000101
11101000
1 14
14 14
13 15
6 11
11 12
15 15
8 15
10 11
7 11
9 14

20
7
9
12
9
8
14
8
11
12

.