Background

土拨鼠文景刚刚学习了质数, 也了解到了互质的概念.

互质_百度百科 (baidu.com)

如果$a, b$互质, 则$a, b$的最大公约数为$1$. 注意$1$和任意整数互质.

Description

给你一个长度为$n$的序列, 元素为$a_i$, 并且给出$q$次询问.

每次询问给你一个区间$[l, r]$, 请输出这个区间的最大值$m$, 并且计算这个区间中有多少个元素跟$m$互质.

Format

Input

第一行输入两个整数$n, q$

第二行输入$n$个正整数$a_i$

接下来$q$行, 每行两个整数$l, r$, 表示询问的区间

Output

输出$q$行, 每行两个整数, 表示$l, r$区间的最大值$m$和区间内与$m$互质元素的个数

Samples

6 3
1 2 3 4 2 4
1 4
1 3
4 6

4 2
3 2
4 0

Limitation

$1 <= n, q <= 10^5, 1<=a_i <= 20, 1<=l <= r<=n$