最小的分数

题目描述

震惊！一道小学数学题竟然90%的人都做不起！

$\frac{12}{11}<\frac{a}{b}<\frac{11}{10}$其中$a,b$均为正整数，要求$a+b$的最小值

最小时$\frac{a}{b}=\frac{23}{21},min\{a+b\}=44$

现在题目有所变化，需要你编程解决

给你四个数$a_1,b_1,a_2,b_2$，你需要找一个分数$\frac{x}{y}$满足$\frac{a_1}{b_1}\le\frac{x}{y}\le\frac{a_2}{b_2}$（注意这里是小于等于，如果把题目变为小于其实也能做，但有更多思考量，推荐你考试后思考）

且$x+y$最小，请输出这个最小值

一共有多组询问，每组询问你都要输出一行答案

你会得知一个数据规模$n$，题目中的所有正整数最大不超过$n$

输入格式

输入一行一个正整数 n，表示数据规模

之后一行一个正整数q，表示一共有q组询问

之后q行，每行4个正整数$a_1,b_1,a_2,b_2$，确保全部的数字都不超过$n$，所有分数都是最简分数，且$\frac{a_1}{b_1}\le\frac{a_2}{b_2}$

输出格式

输出q行，每行一个正整数，表示答案。

样例

样例输入

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

样例输出

2
3
8

样例解释

三个答案分别来自于

$\frac{1}{1}$ $\frac21$ $\frac53$

数据范围

第一个数据点，$n\le10,q\le10$

第二、三个数据点，$n\le100,q\le100$

第四、五、六、七个数据点，$n\le1000,q\le10000$

第八、九、十个数据点，$n\le1000,q\le100000$