Description

给定一个长为 $n$ 的序列 $a_1,a_2,...,a_n$ ，有 $q$ 次查询，每次给定 $\texttt{l r}$ ，求 $\varphi(\prod_{i=l}^{r} a_i)$ 对 $998244353$ 取模的值。

Input

第一行输入 $n$ 和 $q$ 。

第二行输入 $n$ 个数，第 $i$ 个数表示 $a_i$ 。

接下来 $q$ 行，每行读入两个数 $l,r$ ，表示一组询问。

Output

对于每组询问，输出答案。

Samples

• Input #1

  2 3
  114 514
  1 1
  2 2
  1 2
  

• Output #1

  36
  256
  18432
  

• Input #2

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

• Output #2

  2
  8
  32
  

Constriants

本题开启 $subtask$ 。

子任务1 (5分)：$1\le a_i\le 2$ ，时间限制 $3.5s$ ；

子任务2 (5分)：$1\le n,q\le 3000,1\le a_i\le 1000$ ，时间限制 $3.5s$；

子任务3 (10分)：$1\le n,q\le 3000,1\le a_i\le 10^7$ ，时间限制 $3.5s$；

子任务4 (30分)：$1\le n,q\le 10^5, 1\le a_i\le 10^7$ ，时间限制 $3.5s$；

子任务5 (20分)：$1\le n,q\le 10^6 , 1\le a_i\le 10^7$ ，时间限制 $6s$ ；

子任务6 (30分)：$1\le n,q\le 10^ 6 , 1\le a_i\le 10^7$ ，时间限制 $3.5s$ 。