```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	const MAX = 10000010
	spf := make([]int, MAX+1)
	for i := 0; i <= MAX; i++ {
		spf[i] = i
	}
	for i := 2; i*i <= MAX; i++ {
		if spf[i] == i {
			for j := i * i; j <= MAX; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}

	var n int
	fmt.Fscan(in, &n)
	x := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &x[i])
	}

	freq := make(map[int]int)
	for _, xi := range x {
		freq[xi]++
	}

	f := make(map[int]int64)
	for v, fr := range freq {
		prs := getPrimes(v, spf)
		for _, p := range prs {
			f[p] += int64(fr)
		}
	}

	var primes []int
	for p := range f {
		primes = append(primes, p)
	}
	sort.Ints(primes)
	k := len(primes)

	val := make([]int64, k)
	for i := 0; i < k; i++ {
		val[i] = f[primes[i]]
	}

	prefix := make([]int64, k+1)
	for i := 1; i <= k; i++ {
		prefix[i] = prefix[i-1] + val[i-1]
	}

	var m int
	fmt.Fscan(in, &m)
	answers := make([]int64, m)
	for q := 0; q < m; q++ {
		var li, ri int
		fmt.Fscan(in, &li, &ri)
		a := max(li, 2)
		b := min(ri, 10000000)
		if a > b {
			answers[q] = 0
			continue
		}
		l := sort.SearchInts(primes, a)
		r := sort.SearchInts(primes, b+1) - 1
		if l > r {
			answers[q] = 0
		} else {
			answers[q] = prefix[r+1] - prefix[l]
		}
	}

	for _, ans := range answers {
		fmt.Fprintln(out, ans)
	}
}

func getPrimes(v int, spf []int) []int {
	primes := []int{}
	x := v
	for x > 1 {
		p := spf[x]
		primes = append(primes, p)
		for x%p == 0 {
			x /= p
		}
	}
	return primes
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```