Gauss

Είναι μια ελάχιστα γνωστή ιστορία, ότι ο νεαρός Carl Friedrich Gauss ήταν ανήσυχος στην τάξη και έτσι ο δάσκαλός του σκέφτηκε να τον απασχολήσει.

Ο δάσκαλος του έδωσε μια σειρά θετικών ακεραίων ~F(1),\;F(2),\;\ldots,\;F(K)~. Θεωρούμε ~F(t) = 0~ για ~t~ > ~K~. Επιπλέον, του έχει δώσει ένα σύνολο τυχερών αριθμών και την τιμή κάθε τυχερού αριθμού. Εάν το ~X~ είναι ένας τυχερός αριθμός, τότε το ~C(X)~ υποδηλώνει την τιμή του.

Αρχικά, υπάρχει ένας θετικός ακέραιος αριθμός ~A~ γραμμένος στον πίνακα. Σε κάθε κίνηση, ο Carl πρέπει να κάνει ένα από τα παρακάτω πράγματα:

• Εάν ο αριθμός ~N~ είναι γραμμένος επί του παρόντος στον πίνακα, τότε ο Carl μπορεί να γράψει έναν από τους διαιρέτες ~M~, μικρότερο από ~N~, αντί για ~N~. Αν γράψει τον αριθμό ~M~, η τιμή της κίνησης είναι ~F(d(N / M))~, όπου ~d(N/M)~ είναι ο αριθμός των διαιρετών του θετικού ακέραιου ~N/M~ (συμπεριλαμβανομένων των ~N/M~).
• Εάν το ~N~ είναι ένας τυχερός αριθμός, ο Carl μπορεί να αφήσει αυτόν τον αριθμό στον πίνακα και η τιμή της κίνησης είναι ~C(N)~.

Ο Carl πρέπει να κάνει ακριβώς ~L~ κινήσεις και αφού έχει κάνει όλες τις κινήσεις του, ο αριθμός ~B~ πρέπει να γραφτεί στον πίνακα. Ας δηλώσουμε το ~G(A,\;B,\;L)~ ως την ελάχιστη τιμή με την οποία ο Carl μπορεί να το πετύχει αυτό.
Αν δεν είναι δυνατό να κάνουμε ~L~ τέτοιες κινήσεις, ορίζουμε ~G(A,\;B,\;L) = -1~.

Ο δάσκαλος έδωσε Q ερωτήσεις στον Carl. Σε κάθε ερώτημα, ο Carl παίρνει τους αριθμούς ~A~ και ~B~ και πρέπει να υπολογίσει την τιμή ~G(A,\;B,\;L_1) + G(A,\;B,\;L_2) + \ldots + G(A,\;B,\;L_M)~, όπου οι αριθμοί ~L_1,\;\ldots,\;L_M~​είναι ίδιοι για όλα τα ερωτήματα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~K\;(1 \le K \le 10\,000)~.
Η δεύτερη γραμμή περιέχει ~K~ θετικούς ακέραιους αριθμούς ~F(1),\;F(2),\;\ldots,\;F(K)~, που είναι μικρότεροι ή ίσοι του ~1\,000~.
Η ακόλουθη γραμμή περιέχει τον θετικό ακέραιο ~M\;(1 \le M \le 1\,000)~.
Η ακόλουθη γραμμή περιέχει ~M~ θετικούς ακέραιους ~L_1,\;L_2,\;\ldots,\;L_M~, που είναι μικρότεροι ή ίσοι του ~10\,000~.
Η ακόλουθη γραμμή περιέχει τον θετικό ακέραιο ~T~, τον συνολικό αριθμό των τυχερών αριθμών ~(1 \le T \le 50)~.
Κάθε μία από τις ακόλουθες γραμμές ~T~ περιέχει τους αριθμούς ~X~ και ~C(X)~ που δηλώνουν ότι το ~X~ είναι ένας τυχερός αριθμός και το ~C(X)~ είναι η τιμή του ~(1 \le X \le 1\,000\,000, 1 \le C(X) \le 1\,000)~.
Κάθε τυχερός αριθμός εμφανίζεται το πολύ μία φορά.
Η ακόλουθη γραμμή περιέχει τον θετικό ακέραιο ~Q\;(1 \le Q \le 50\,000)~.
Κάθε μία από τις ακόλουθες ~Q~ γραμμές περιέχει 2 θετικούς ακέραιους αριθμούς ~A~ και ~B\;(1 \le A, B \le 1\,000\,000)~.

Έξοδος

Πρέπει να τυπώσετε ~Q~ γραμμές. Η ~i~-οστή γραμμή περιέχει την απάντηση στο ~i~-οστό ερώτημα.

Παραδείγματα

input

4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2

output

7

Επεξήγηση του 1ου παραδείγματος:

~L_1 = 1~, οπότε ο Carl μπορεί να κάνει ακριβώς μία κίνηση - αντικαταστήστε τον αριθμό 4 με τον αριθμό 2, άρα ~G(4,\;2,\;1) = F(d(2)) = 1~.
~L_2 = 2~, οπότε ο Carl έχει δύο επιλογές:

• Μπορεί να αντικαταστήσει τον αριθμό 4 με τον αριθμό 2 και μετά να αφήσει τον αριθμό 2 (γιατί είναι τυχερός αριθμός), οπότε πληρώνει την τιμή ~F(d(4/2)) + C(2) = 1 + 5 = 6~
• Μπορεί να αφήσει τον αριθμό 4 στην πρώτη κίνηση και να τον αντικαταστήσει στη δεύτερη κίνηση με τον αριθμό 2, οπότε η τιμή είναι ~C(4) + F(d(4/2)) = 10 + 1 = 11~
  Η πρώτη επιλογή κοστίζει λιγότερο, επομένως ~G(4,\;2,\;2) = 6~.
  Η απάντηση στο ερώτημα είναι ~G(4,\;2,\;1) + G(4,\;2,\;2) = 7~.

input

3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68

output

118
-2

input

3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1

output

16
66