| 问题描述 |
|---|
令f(x)表示一个正整数x的所有质因数的和。 有m个正整数保存在长度为m的数组a中，给定两个合法下标c和d，输出下标范围内所有数组元素x的f(x)值的总和，即f(a[c])+f(a[c+1])+...+f(a[d])。 |
| 输入描述 |
单组案例。 一个正整数m，表示数组元素的个数，（m<=100000） 然后是m个正整数，表示数组每个元素的值，（均不大于1e+7） 接下来是一个正整数q，表示有q次查询，（q<=100000） 每次查询占一行，由两个非负整数c和d组成，表示需要参与计算的元素的下标范围从c到d。（0<=c<=d<=m-1） |
| 输出描述 |
针对每次查询，输出一个长整数，表示f(a[c])+f(a[c+1])+...+f(a[d])的值。 每次查询结果输出完要换行。 |
| 样例输入复制样例 |
5 2 6 7 9 3 2 0 2 1 4 |
| 样例输出 |
14 18 |
| 提示说明 |
f(2)=2，f(6)=2+3=5，f(7)=7，f(9)=3，f(3)=3 第一次查询查前三个数字，2+5+7=14 第一次查询查后四个数字，5+7+3+3=18 |
| 相关 |