Problem Description

前情回顾：

定义一个数组的权值和为：假设数组乘积为S，数组的权值和为使得x*y=S的所有(x,y)对数(x, y均为正整数)
给你一个数组A，请你求出他的所有非空子序列的权值和，由于答案可能很大，请对998244353取模
例如S=2, 那么就有2对(x, y)符合要求, 分别为(1, 2), (2, 1)

现在小L希望知道某个子数组的权值和，但是他不会做，所以他来询问你了，你能帮帮他吗？
子数组是数组的一段连续区间，例如$[1,2]$是数组$[1,2,3]$的子数组

Input Format

第一行两个个整数$n,q$，代表数组大小和询问个数
第二行$n$个整数，表示给定的数组$A$ 接下来$q$行，每行两个整数$l, r$代表询问的区间

Output Format

对于每个询问，输出一个整数，表示答案

Sample

输入样例1

2 1
1 2
1 2

输出样例1

5

Hint

$1 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq a_i \leq 10^9, 1 \leq l \leq r \leq n$ 保证所有$a_i$均为1或质数