Bittimaassa on n kaupunkia, joiden välillä on m tietä. Tehtäväsi on vastata kyselyihin, mikä on lyhin reitti kaupungista toiseen.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, m ja q: kaupunkien määrä, teiden määrä ja kyselyiden määrä.

Sitten syötteessä on m riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua a, b ja c: kaupunkien a ja b välillä on tie, jonka pituus on c. Kaikki tiet ovat kaksisuuntaisia.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b: reitin tulee kulkea kaupungista a kaupunkiin b.

Tuloste

Tulosta jokaiseen kyselyyn, kuinka pitkä on lyhin reitti kaupunkien välillä. Jos kaupunkien välillä ei ole mitään reittiä, tulosta "QAQ".

Rajat

• 1 \le n \le 500
• 1 \le m \le n^2
• 1 \le q \le 10^5
• 1 \le a,b \le n
• 1 \le c \le 10^9

Esimerkki

Syöte:

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Tuloste:

5
5
8
QAQ
3