International Connecting Passage Causeway 是一条漫长且坑洼不平的双向乡村公路，在不同地点与多条街道相交。

这里有许多司机，每位司机都会沿着这条乡村公路行驶，从某个路口出发，并在另一个路口结束。对于每位司机，请问他们会经过多少个路口？

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 10^5$) 和 $q$ ($1 \le q \le 10^5$)，其中 $n$ 是交叉街道的数量，$q$ 是司机的数量。

接下来的 $n$ 行，每行包含一个长度不超过 10 的小写字母字符串，表示与乡村公路相交的街道名称。所有街道名称都是唯一的。沿着乡村公路的某个方向行驶，看到的街道顺序与输入给出的顺序完全一致。

接下来的 $q$ 行，每行包含两个长度不超过 10 的小写字母字符串，表示每位司机的起始路口和结束路口。查询将在不同的街道之间进行。

输出格式

输出 $q$ 行，第 $i$ 行包含第 $i$ 位司机经过的路口数量。

样例

样例输入 1

3 3
first
second
third
first second
third first
second third

样例输出 1

0
1
0