该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

ztm 突然发现自己老家的街边经常有人在使用一种很神奇的工具——粮食放大器

粮食放大器据说是我国密不外传的古老技术，把一小勺玉米粒放进去，过一会，砰地一声，就能产出一大堆爆米花。

ztm 觉得如果这个技术能再进一步进行改进，那么大家就有取之不尽用之不竭的粮食了！

经过 ztm 不断的努力，终于在梦里实现了这个梦想

在梦里，ztm 设计了一款真正的粮食放大器，这个粮食放大器可以将一种粮食变成几倍的另一种粮食

ztm 总结了一个表格 $a_{i,j}$ 来表示粮食放大器的作用，代表着将 $1$ 单位的 $i$ 类粮食放入粮食放大器后可以产生 $a_{i,j}$ 单位的 $j$ 类粮食

例如如果有两种粮食 $a_{1,2} = 3, a_{2,1} = 2$，那么就意味着

$1$ 单位的 $1$ 号粮食通过粮食放大器可以变成 $3$ 单位的 $2$ 号粮食

接着再将这 $3$ 单位的 $2$ 号粮食放进粮食放大器，就可以变成 $6$ 单位的 $1$ 号粮食

这样通过 $2$ 次放大就可以将 $1$ 号粮食翻 $6$ 倍！

随着粮食放大器的成功，ztm 决定帮助贫困村庄将他们当地的粮食不断放大！

现在 ztm 总共找到了 $q$ 个贫困村庄

第 $i$ 个村庄一开始都只有 $1$ 单位的 $x_i$ 号粮食，ztm 希望通过粮食放大器，让这个村庄拥有至少 $2^{k_i}$ 个单位的 $x_i$ 号粮食

ztm 现在想知道，对于每个村庄，他的粮食放大器需要工作几次？

输入格式

第一行两个整数$n,q$，表示粮食的种类，以及村庄的个数。

接下来 $n$ 行，每行$n$个整数，第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$，含义如题

接下来 $q$ 行，每行两个整数 $x_i,k_i$，表示第 $i$ 个村庄的信息，含义如题

输出格式

对于每个村庄输出一个整数，表示在这个村庄，粮食放大器需要工作的次数

数据范围

对于 $10\%$ 的测试数据，满足$1\leq n\leq 10,q=1,1\leq k\leq20$; 对于 $30\%$ 的测试数据，满足$1\leq n\leq 100,1\leq q\leq10,1\leq k\leq20$; 对于 $60\%$ 的测试数据，满足$1\leq n\leq 100,1\leq q\leq10,1\leq k\leq10^5$ 对于 $80\%$ 的测试数据，满足$1\leq n\leq 100,1\leq q\leq10^2,1\leq k\leq 10^5$; 对于 $100\%$ 的测试数据，满足$1\leq n\leq 100,1\leq q\leq 10^3,1\leq k \leq10^5,0\leq a_{i,j}\leq10$,保证答案不大于$10^6$;

样例输入

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

样例输出

3
5
6