定义一个二元组 是漂亮二元组，当且仅当 且 和 的因子数量相等。 给定一个长度为 的正整数序列 ，以及 次询问。 每次询问给出一个区间 ，请输出区间中漂亮二元组的数量。

输入描述:

第一行有两个正整数  和  。第二行有  个正整数  。随后  行，每行两个整数  。

输出描述:

输出  行，每行一个整数，代表漂亮二元组的数量。