说明

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

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

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

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

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

hhc 总结了一个表格 $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$ 倍！

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

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

3
5
6