#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int NMAX = 30000;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
typedef long long ll;
int n, m;
int coeff[NMAX];
void InitCoeff(){
for (int i = n + 1; i >= 2; i--){
coeff[i - 2] = 1;
for (int j = i * 2; j <= n+1; j += i){
coeff[i-2] -= coeff[j - 2];
}
}
}
struct frac{
ll num;
ll den;
bool operator<(const frac& rhs) const{
ll a = num * rhs.den;
ll b = rhs.num * den;
return a < b;
}
bool operator>(const frac& rhs) const{
ll a = num * rhs.den;
ll b = rhs.num * den;
return a > b;
}
bool operator==(const frac& rhs) const{
ll a = num * rhs.den;
ll b = rhs.num * den;
return a == b;
}
frac operator+(const frac& rhs) const{
ll a = num * rhs.den;
ll b = rhs.num * den;
return{ a + b, den*rhs.den };
}
frac operator-(const frac& rhs) const{
ll a = num * rhs.den;
ll b = rhs.num * den;
return{ a - b, den*rhs.den };
}
};
const ll B = 1000000007;
ll count(frac f, frac l){
frac a = f - l;
a.num = max(a.num, 0LL);
frac b = f + l;
b.num = min(b.num, b.den - 1);
ll ret = 0;
FOR(i, 2, n + 2){
ret -= ((a.num*i) / a.den)*coeff[i - 2];
ret += ((b.num*i) / b.den)*coeff[i - 2];
}
return ret;
}
int main(){
scanf("%d%d", &n, &m);
InitCoeff();
REP(_, m){
frac s;
ll k;
scanf("%lld%lld%lld", &s.num, &s.den, &k);
ll l = 1, r = B;
while (r - l > 1)
{
ll c = count(s, { (l + r) / 2, B });
if (c == k){
l = (l + r) / 2;
break;
}
else if (c < k){
l = (l + r) / 2;
}
else{
r = (l + r) / 2;
}
}
frac maxdist = s;
frac dif = { 0, 1 };
frac a = s - frac{ l, B };
a.num = max(a.num, 0LL);
frac b = s + frac{ l, B };
b.num = min(b.num, b.den - 1);
FOR(i, 2, n + 2){
frac f = { ((a.num*i) / a.den) + 1, i };
if (s - f > dif){
dif = s - f;
maxdist = f;
}
f = { ((b.num*i) / b.den), i };
if (f - s > dif){
dif = f - s;
maxdist = f;
}
}
printf("%lld\n", maxdist.den - 1);
}
}
I2RlZmluZSBfQ1JUX1NFQ1VSRV9OT19XQVJOSU5HUwojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG1hdGguaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTk1BWCA9IDMwMDAwOwoKI2RlZmluZSBGT1IoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCiNkZWZpbmUgUkVQKGksYikgRk9SKGksMCxiKQoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CgppbnQgbiwgbTsKCmludCBjb2VmZltOTUFYXTsKdm9pZCBJbml0Q29lZmYoKXsKCWZvciAoaW50IGkgPSBuICsgMTsgaSA+PSAyOyBpLS0pewoJCWNvZWZmW2kgLSAyXSA9IDE7CgkJZm9yIChpbnQgaiA9IGkgKiAyOyBqIDw9IG4rMTsgaiArPSBpKXsKCQkJY29lZmZbaS0yXSAtPSBjb2VmZltqIC0gMl07CgkJfQoJfQp9CgpzdHJ1Y3QgZnJhY3sKCWxsIG51bTsKCWxsIGRlbjsKCWJvb2wgb3BlcmF0b3I8KGNvbnN0IGZyYWMmIHJocykgY29uc3R7CgkJbGwgYSA9IG51bSAqIHJocy5kZW47CgkJbGwgYiA9IHJocy5udW0gKiBkZW47CgkJcmV0dXJuIGEgPCBiOwoJfQoJYm9vbCBvcGVyYXRvcj4oY29uc3QgZnJhYyYgcmhzKSBjb25zdHsKCQlsbCBhID0gbnVtICogcmhzLmRlbjsKCQlsbCBiID0gcmhzLm51bSAqIGRlbjsKCQlyZXR1cm4gYSA+IGI7Cgl9Cglib29sIG9wZXJhdG9yPT0oY29uc3QgZnJhYyYgcmhzKSBjb25zdHsKCQlsbCBhID0gbnVtICogcmhzLmRlbjsKCQlsbCBiID0gcmhzLm51bSAqIGRlbjsKCQlyZXR1cm4gYSA9PSBiOwoJfQoJZnJhYyBvcGVyYXRvcisoY29uc3QgZnJhYyYgcmhzKSBjb25zdHsKCQlsbCBhID0gbnVtICogcmhzLmRlbjsKCQlsbCBiID0gcmhzLm51bSAqIGRlbjsKCQlyZXR1cm57IGEgKyBiLCBkZW4qcmhzLmRlbiB9OwoJfQoJZnJhYyBvcGVyYXRvci0oY29uc3QgZnJhYyYgcmhzKSBjb25zdHsKCQlsbCBhID0gbnVtICogcmhzLmRlbjsKCQlsbCBiID0gcmhzLm51bSAqIGRlbjsKCQlyZXR1cm57IGEgLSBiLCBkZW4qcmhzLmRlbiB9OwoJfQp9OwoKY29uc3QgbGwgQiA9IDEwMDAwMDAwMDc7CmxsIGNvdW50KGZyYWMgZiwgZnJhYyBsKXsKCWZyYWMgYSA9IGYgLSBsOwoJYS5udW0gPSBtYXgoYS5udW0sIDBMTCk7CglmcmFjIGIgPSBmICsgbDsKCWIubnVtID0gbWluKGIubnVtLCBiLmRlbiAtIDEpOwoJbGwgcmV0ID0gMDsKCUZPUihpLCAyLCBuICsgMil7CgkJcmV0IC09ICgoYS5udW0qaSkgLyBhLmRlbikqY29lZmZbaSAtIDJdOwoJCXJldCArPSAoKGIubnVtKmkpIC8gYi5kZW4pKmNvZWZmW2kgLSAyXTsKCX0KCXJldHVybiByZXQ7Cn0KCmludCBtYWluKCl7CglzY2FuZigiJWQlZCIsICZuLCAmbSk7CglJbml0Q29lZmYoKTsKCVJFUChfLCBtKXsKCQlmcmFjIHM7CgkJbGwgazsKCQlzY2FuZigiJWxsZCVsbGQlbGxkIiwgJnMubnVtLCAmcy5kZW4sICZrKTsKCQlsbCBsID0gMSwgciA9IEI7CgkJd2hpbGUgKHIgLSBsID4gMSkKCQl7CgkJCWxsIGMgPSBjb3VudChzLCB7IChsICsgcikgLyAyLCBCIH0pOwoJCQlpZiAoYyA9PSBrKXsKCQkJCWwgPSAobCArIHIpIC8gMjsKCQkJCWJyZWFrOwoJCQl9CgkJCWVsc2UgaWYgKGMgPCBrKXsKCQkJCWwgPSAobCArIHIpIC8gMjsKCQkJfQoJCQllbHNlewoJCQkJciA9IChsICsgcikgLyAyOwoJCQl9CgkJfQoJCWZyYWMgbWF4ZGlzdCA9IHM7CgkJZnJhYyBkaWYgPSB7IDAsIDEgfTsKCQlmcmFjIGEgPSBzIC0gZnJhY3sgbCwgQiB9OwoJCWEubnVtID0gbWF4KGEubnVtLCAwTEwpOwoJCWZyYWMgYiA9IHMgKyBmcmFjeyBsLCBCIH07CgkJYi5udW0gPSBtaW4oYi5udW0sIGIuZGVuIC0gMSk7CgkJRk9SKGksIDIsIG4gKyAyKXsKCQkJZnJhYyBmID0geyAoKGEubnVtKmkpIC8gYS5kZW4pICsgMSwgaSB9OwoJCQlpZiAocyAtIGYgPiBkaWYpewoJCQkJZGlmID0gcyAtIGY7CgkJCQltYXhkaXN0ID0gZjsKCQkJfQoJCQlmID0geyAoKGIubnVtKmkpIC8gYi5kZW4pLCBpIH07CgkJCWlmIChmIC0gcyA+IGRpZil7CgkJCQlkaWYgPSBmIC0gczsKCQkJCW1heGRpc3QgPSBmOwoJCQl9CgkJfQoJCXByaW50ZigiJWxsZFxuIiwgbWF4ZGlzdC5kZW4gLSAxKTsKCX0KfQ==