Танд \( N \) ширхэг бүхэл тоо өгөгдөнө.

Бид дараах функцийг тодорхойлъё:

• \(f(x) : x\) тооны өөрөөс нь ялгаатай хамгийн их хуваагч

Жишээ:

• \(f(10) = 5\)
• \(f(12) = 6\)
• \(f(17) = 1\)

Танд 'Q' ширхэг асуулга өгөгдөнө.

Асуулга бүр дараах хэлбэртэй:

• L R — L -ээс R хүртэлх (хоёр захыг багтаасан) интервал дахь бүх тоонуудын f(x) -ийн нийлбэрийг ол.

Оролт:

• Эхний мөрөнд бүхэл тоонуудыг тоо болох N, асуулгын тоо болох Q хоосон зайгаар тусгаарлан өгөгдөнө.

• Дараагийн мөрөнд N ширхэг бүхэл тоо:

a₁ a₂ a₃ ... aₙ

- Дараагийн Q мөр бүрт:

L R

Гаралт:

• Асуулга бүрийн хариуг тус бүр нэг мөрөнд хэвлэнэ

Хязгаарлалтууд:

• \(1 \le Q \le 10^5\)
• \(1 < x < 10^{12}\)

Дэд бодлого

Жишээ:

Оролт-1

5 3
10 12 7 8 9
1 3
2 5
3 3

Гаралт-1

12
14
1

Оролт-2

4 2
5 2 3 4
1 4
2 3

Гаралт-2

5
2