中国剩余定理如何应用于模板题的解题过程？

本文共计1111个文字，预计阅读时间需要5分钟。

Description: 我知道部分同学最近在研究中国剩余定理，这个定理本身，其实是比较简单的：假设有两两互质的正整数，下面同余方程组：在+内含有唯一解。记Mi=m_i/(m_i)，因为(M_i，m_i)=(1)，所以+。

Description：

我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的： 假设两两互素，则下面同余方程组：

• …
• 在内有唯一解。 记Mi=M/m_{i}(1<=i<=k),因为（M_{i},m_{i}）=1,故有二个整数满足,如果记 ,那么会有： 很显然，就是方程组的一个解，这个解加减的整数倍后就可以得到最小非负整数解。 这就是中国剩余定理及其求解过程。 现在有一个问题是这样的： 一个正整数除以余，除以余, 除以余,总之， 除以余,其中,求满足条件的最小的数。

Input

输入数据包含多组测试实例，每个实例的第一行是两个整数和,其中，I表示M的个数，的含义如上所述，紧接着的一行是个整数 并且结束输入，不处理。

Output

对于每个测试实例，请在一行内输出满足条件的最小的数。每个实例的输出占一行。