Background

Description

C++-数学-被整除

整除是指整数a除以自然数b除得的商正好是整数而余数是零．我们就说a能被b整除（或说b能整除a），记作b|a，读作“b整除a”或“a能被b整除”．它与除尽既有区别又有联系．除尽是指数a除以数b（b≠0）所得的商是整数或有限小数而余数是零时，我们就说a能被b除尽（或说b能除尽a）．因此整除与除尽的区别是，整除只有当被除数、除数以及商都是整数，而余数是零．除尽并不局限于整数范围内，被除数、除数以及商可以是整数，也可以是有限小数，只要余数是零就可以了．它们之间的联系就是整除是除尽的特殊情况．

整除的一些性质为：

（1）如果a与b都能被c整除，那么a+b与a-b也能被c整除．

（2）如果a能被b整除，c是任意整数，那么积ac也能被b整除．

（3）如果a同时被b与c整除，并且b与c互质，那么a一定能被积bc整除．反过来也成立．

Format

Input

Output

Samples

Limitation

1s, 1024KiB for each test case.