U607642 gcd之和 加强版

题目名：gcd 子文件夹名：sumgcd_jqb 时间限制：$25ms - 500ms$ 其中： - Subtask #1 $500ms$ - Subtask #2 $300ms$ - Subtask #3 $20ms$ 备注：本题的 $30ms$ 为正解在洛谷评测机的用时，现实中可能会慢一些。所以请选手放心，本题有正解，但是在正式考试（如CSP），可能做不到 $30ms$。（开O2才可以AC）

对任意正整数 $x$，定义 $f(x)=x$ 的十进制各位数中非零的数字的乘积。例如 $f(1024)=8$。 现给定正整数序列 $a_1..a_n$，要求依次回答 $q$ 个问询：在 $f(a_l)..f(a_r)$ 中任选下标不同的 $2$ 个（不计顺序），求所有选法的两个数的 $gcd$ 的总和。形式化地：$\sum_{l\le i

第 $1$ 行 $2$ 个正整数 $n,q$。 第 $2$ 行 $n$ 个正整数 $a_1..a_n$。 后 $q$ 行每行 $2$ 个正整数 $l,r$。

$q$ 行每行 $1$ 个整数表示答案。

子任务1：特殊性质：$n,q \le 100$。 子任务2：特殊性质：$a_i \le 9$。 子任务3：$1 \le l \le r \le n \le 10000，q \le 200，1 \le a_i \le 1000$。 数据仅作为梯度显示，测试时采用捆绑数据测试。