求餘數

求餘數對於會寫程式的人來說，是個簡單的問題，例如用VB 來求餘數時，可以用mod這個關鍵字來實作。但如果算式為R = B^P mod M 的型態，給B、P、及M，要算出餘數R，當B 或P 很大時，那就變得不簡單了。現在，請你設計一個程式，來解決上述這個不簡單的問題。

輸入說明：

第一行的數字，表示有幾個問題要求解，第二行開始的每一行，為一個獨立的問題。每一行包含三個數字，分別為B、P、及M，例如：10 2009 9 代表B=10、P=2009、M=9。所有數字均為正整數，其範圍屬於[1,100000]。

輸出說明：

對輸入的每個問題分別以一行輸出餘數R。

輸入範例：

2

10 2009 9

2 99 5

輸出範例:
1
3