```go
package main

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

type Uint64Slice []uint64

func (x Uint64Slice) Len() int           { return len(x) }
func (x Uint64Slice) Less(i, j int) bool { return x[i] < x[j] }
func (x Uint64Slice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buffer := make([]byte, 1024*1024)
	scanner.Buffer(buffer, 1024*1024)

	nextInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	resN := 0
	for _, b := range scanner.Bytes() {
		resN = resN*10 + int(b-'0')
	}
	n := resN
	q := nextInt()

	maxA := 1000005
	spf := make([]int, maxA+1)
	for i := 2; i <= maxA; i++ {
		spf[i] = i
	}
	for i := 2; i*i <= maxA; i++ {
		if spf[i] == i {
			for j := i * i; j <= maxA; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}

	parent := make([]int, maxA+1)
	for i := 1; i <= maxA; i++ {
		parent[i] = i
	}

	find := func(i int) int {
		root := i
		for parent[root] != root {
			root = parent[root]
		}
		curr := i
		for curr != root {
			nxt := parent[curr]
			parent[curr] = root
			curr = nxt
		}
		return root
	}

	union := func(i, j int) {
		rootI := find(i)
		rootJ := find(j)
		if rootI != rootJ {
			parent[rootI] = rootJ
		}
	}

	hasPrime := make([]bool, maxA+1)
	a := make([]int, n+1)

	for i := 1; i <= n; i++ {
		a[i] = nextInt()
		v := a[i]
		for v > 1 {
			p := spf[v]
			hasPrime[p] = true
			union(a[i], p)
			for v%p == 0 {
				v /= p
			}
		}
	}

	pairs := make([]uint64, 0, n*21)

	for i := 1; i <= n; i++ {
		S := make([]int, 0, 8)
		S = append(S, find(a[i]))

		v := a[i] + 1
		for v > 1 {
			p := spf[v]
			if hasPrime[p] {
				S = append(S, find(p))
			}
			for v%p == 0 {
				v /= p
			}
		}

		for j := 0; j < len(S); j++ {
			for k := j + 1; k < len(S); k++ {
				u, v := S[j], S[k]
				if u == v {
					continue
				}
				if u > v {
					u, v = v, u
				}
				pairs = append(pairs, (uint64(u)<<32)|uint64(v))
			}
		}
	}

	sort.Sort(Uint64Slice(pairs))

	var uniquePairs []uint64
	if len(pairs) > 0 {
		uniquePairs = make([]uint64, 0, len(pairs))
		uniquePairs = append(uniquePairs, pairs[0])
		for i := 1; i < len(pairs); i++ {
			if pairs[i] != pairs[i-1] {
				uniquePairs = append(uniquePairs, pairs[i])
			}
		}
	}
	pairs = uniquePairs

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for qIdx := 0; qIdx < q; qIdx++ {
		s := nextInt()
		t := nextInt()

		u := find(a[s])
		v := find(a[t])

		if u == v {
			fmt.Fprintln(out, 0)
			continue
		}

		if u > v {
			u, v = v, u
		}

		key := (uint64(u) << 32) | uint64(v)

		idx := sort.Search(len(pairs), func(i int) bool {
			return pairs[i] >= key
		})

		if idx < len(pairs) && pairs[idx] == key {
			fmt.Fprintln(out, 1)
		} else {
			fmt.Fprintln(out, 2)
		}
	}
}
```