#include <bits/stdc++.h>
using namespace std;
struct Intrebare {
int nod_1 , nod_2 , stanga , dreapta , indice;
} intrebare[100001];
int reprezentant[100001] , grad[100001] , rezultat[100001];
inline int Radacina (const int nod)
{
return reprezentant[nod] ? (reprezentant[nod] = Radacina(reprezentant[nod])) : nod;
}
inline void Unire (int nod_1 , int nod_2)
{
if ((nod_1 = Radacina(nod_1)) == (nod_2 = Radacina(nod_2)))
{ return; }
if (grad[nod_1] < grad[nod_2])
{ swap(nod_1 , nod_2); }
grad[nod_1] += (grad[nod_1] == grad[nod_2] ? 1 : 0);
reprezentant[nod_2] = nod_1;
}
inline void Solve ()
{
int numar_noduri , limita , numar_intrebari;
cin >> numar_noduri >> limita >> numar_intrebari;
for (int indice = 1 ; indice <= numar_intrebari ; indice++)
{
cin >> intrebare[indice].nod_1 >> intrebare[indice].nod_2;
if (intrebare[indice].nod_1 > intrebare[indice].nod_2)
{ swap(intrebare[indice].nod_1 , intrebare[indice].nod_2); }
intrebare[indice].stanga = 1;
intrebare[indice].dreapta = intrebare[indice].nod_1 + 1;
intrebare[indice].indice = indice;
}
for (int ramas = numar_intrebari ; ramas ; )
{
sort(intrebare + 1 , intrebare + ramas + 1 , [] (Intrebare& optiune_1 , Intrebare& optiune_2) -> bool {
return optiune_1.stanga + optiune_1.dreapta > optiune_2.stanga + optiune_2.dreapta;
});
for (int indice = limita , __indice = 1 ; __indice <= ramas ; indice--)
{
for (int candidat = (indice << 1) ; candidat <= numar_noduri ; candidat += indice)
{ Unire(indice , candidat); }
while (__indice <= ramas && (intrebare[__indice].stanga + intrebare[__indice].dreapta) / 2 == indice) {
if (Radacina(intrebare[__indice].nod_1) == Radacina(intrebare[__indice].nod_2)) { intrebare[__indice].stanga = indice + 1; }
else { intrebare[__indice].dreapta = indice - 1; }
__indice++;
}
}
for (int indice = 1 ; indice <= numar_noduri ; indice++)
{ reprezentant[indice] = grad[indice] = 0; }
int __ramas = 0;
for (int indice = 1 ; indice <= ramas ; indice++) {
if (intrebare[indice].stanga <= intrebare[indice].dreapta)
{ swap(intrebare[++__ramas] , intrebare[indice]); }
}
ramas = __ramas;
}
for (int indice = 1 ; indice <= numar_intrebari ; indice++)
{ rezultat[intrebare[indice].indice] = limita - intrebare[indice].dreapta + 1; }
for (int indice = 1 ; indice <= numar_intrebari ; indice++)
{ cout << rezultat[indice] << '\n'; }
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_teste = 1;
// cin >> numar_teste;
while (numar_teste--)
{ Solve(); }
return 0;
}
