在火山高校中，數學老師魔方陣不滿學生的素質低落，於是出了一堆數學作業要大家回去寫，沒有寫出來的就開除學籍。大家都嚇了一跳，尤其是功課一向不怎麼好的金英俊。不過在當他們看到題目的標題就笑了出來，因為題目就是連國小生都會求的最大公因數問題！可是就在他們看到了題目的數字以後，大家的下巴就掉了下來。題目中的數字都是天文數字，想必今天晚上是必要「輾轉」難眠的算出答案了。身為金英俊好友的你可否幫他寫個程式處理這個問題呢？

首先在經過詳細觀察過題目之後你發現了以下幾個特性：

1. 每一題的題目都是下面的樣子
   Gcd(a^m – b^m, aⁿ –bⁿ) 除以某個數 p 的餘數
2. 0 < b < a <=1000, 1< m < n<=200, 1 < p <= 10000
3. a 和 b 都互質

5 4 3 6 1000
37 17 50 20 2
889 73 2 34 8115

61
0
5952