### 问题描述 某个部落中包含了许多独立的村落，而村落有各自的烹饪传统。这些传统烹饪法则不仅仅是食物的制作，更多的是与时间的关系。由于不同的村落将会制作不同的食物，所以每个村落都有独一无二的烹饪时间。 每个村落的烹饪法则是这样的：有一个烹饪计时器，每隔固定的时间就会更新一次烹饪进度。当计时器显示值等于其计时周期，则表示烹饪完成，同时计时器将重新开始下一轮的计时。每个村落的计时器都有自己的时间周期 $a_i$ 和初始进度 $b_i$，表示完成一个食物所需的时间和食物开始烹饪时的进度。 每到部落的纪念日他们都会组织一场盛大的宴会，由于部落族群非常多，而且有些村落距离非常遥远，所以酋长打算将所有部落组成 $m$ 个分组，每个组合内的村落举办自己分组内的宴会。他们想知道对于每个分组，为了使所有的菜肴都同时完成，他们需要等待多少时间？你能帮忙解决这个问题吗？ ### 输入格式 第一行包含一个整数 $n$ 表示所有村落分组的数量。 对于每个分组，第一行输入一个整数 $m$ 表示该分组内的村落数量。 接下来 $m$ 行，每行两个整数 $a_i, b_i$，表示该村落烹饪计时器的一个周期为 $a_i$ 小时，初始进度为 $b_i$ 小时，题目保证每个分组内的每个周期互质。 ### 输出格式 输出共有 $n$ 行，对每个村落分组输出包含一个正整数，表示等待多少小时后，该分组所有的菜肴都将同时完成。 ### 样例输入 ``` 2 3 3 1 5 2 7 1 2 7 6 2 1 ``` ### 样例输出 ``` 83 1 ``` ### 样例说明 第一行的 $2$ 表示部落包含两个分组。 第二行的 $3$ 表示第一个分组包含三个村庄。接下来的 $3$ 行表示 $3$ 个村庄的烹饪周期分别为 $3,5,7$，且各自烹饪进度为 $1,2,1$。则这组村庄至少还需要 $83$ 小时才能同时完成烹饪。 而接下来的一组两个村庄的烹饪周期为 $7$ 和 $2$，但是由于初始烹饪进度为 $6$ 和 $1$，所以只需再过一个小时就可以同时完成烹饪。 ### 测评数据规模 $1\leq n,m \leq 10$，$0 \leq b_i\lt a_i\leq 10^3$，$1 \leq \prod a_i \leq 10^{18}$。