seuOJ412 - 珂朵莉的问题

题目描述

『在太阳西斜的这个世界里』—Broken Chronograph—\color{#2CA9E1}\mathsf{『在太阳西斜的这个世界里』}\\\scriptsize\mathsf{—Broken\ Chronograph—} 『置身天上之森』—Late Autumn Night′s Dream—\color{#2CA9E1}\mathsf{『置身天上之森』}\\\scriptsize\mathsf{—Late\ Autumn\ Night's\ Dream—} 『等这场战争结束之后』—StarryRoad To Tomorrow—\color{#2CA9E1}\mathsf{『等这场战争结束之后』}\\\scriptsize\mathsf{—Starry Road\ To\ Tomorrow—} 『不归之人与望眼欲穿的人们』—Dice In Pot—\color{#2CA9E1}\mathsf{『不归之人与望眼欲穿的人们』}\\\scriptsize\mathsf{—Dice\ In\ Pot—} 『人人本着正义之名』—From Down Till Dusk—\color{#2CA9E1}\mathsf{『人人本着正义之名』}\\\scriptsize\mathsf{—From\ Down\ Till\ Dusk—} 『长存不灭的过去，逐渐消逝的未来』—No NewsWas Good News—\color{#2CA9E1}\mathsf{『长存不灭的过去，逐渐消逝的未来』}\\\scriptsize\mathsf{—No\ News Was\ Good\ News—} 『我回来了』—Home , Sweet Home—\color{#E4671E}\mathsf{『我回来了』}\\\scriptsize\mathsf{—Home\ ,\ Sweet\ Home—} 『纵使日薄西山』—Slight Light, Slight Hope—\color{#E4671E}\mathsf{『纵使日薄西山』}\\\scriptsize\mathsf{—Slight\ Light,\ Slight\ Hope—} 『即使看不到未来』—Moonlight Sorcery—\color{#E4671E}\mathsf{『即使看不到未来』}\\\scriptsize\mathsf{—Moonlight\ Sorcery—} 『此时此刻的光辉』—My Happiness—\color{#E4671E}\mathsf{『此时此刻的光辉』}\\\scriptsize\mathsf{—My\ Happiness—} 『盼君勿忘』—Evidence of Existance—\color{#E4671E}\mathsf{『盼君勿忘』}\\\scriptsize\mathsf{—Evidence\ of\ Existance—}

珂朵莉并不会谈恋爱，所以她想问你一个数学题。

珂朵莉给了你一个长度为nn的序列aa，她还有qq个问题问你，对于每个问题，她会给你一个区间[l,r][l,r]，你可以选择任何一个质数bb，她想请你求出区间内可以整除bb的数字个数乘以bb的最大值。

质数指的是：一个大于11的自然数，除了11和它自身外，不能被其他自然数整除的数。

举个例子，比如区间内有数字2,3,4,82,3,4,8，那么选择b=2b=2的结果为2×3=62\times3=6，而选择b=3b=3的结果为1×3=31\times3=3，选择bb为其他质数的结果都为00。

输入格式

第一行，一个整数n(1≤n≤105)n(1\leq n \leq 10^5)，代表序列长度。
接下来一行nn个整数，代表序列a(2≤ai≤109)a(2\leq a_i\leq 10^9)。
第三行，一个整数q(1≤q≤105)q(1\leq q \leq 10^5)，代表问题个数。
接下来qq行，每行两个整数l,r(1≤l≤r≤n)l,r(1\leq l \leq r \leq n)，代表一次[l,r][l,r]上的询问。

输出格式

对于每次询问，输出一行数字表示答案。

样例

输入样例

10
2 3 5 7 9 10 6 3 20 21
5
4 7
7 9
5 6
9 10
1 1

输出样例

7
6
5
7
2

数据范围与提示

请注意此题较为特殊的时间与空间限制。

数据已加强(update on 2023.3.12)