Програмчлалын олимпиадын бодлогын архив

Аватар хөтөлбөр сүйрсний дараа Пандора гаригийнхан ер нь Дэлхийн хүмүүст итгэх хэрэггүй юм гэж шийджээ. Ингээд гаригийн Моднуудын сүлжээнд нэвтрэх эрхийг маш өндөр нууцлалтай болсон байна.

Гэхдээ Дэлхийн онцгой тагнуул Бондын ачаар уг нууцлалын гол түлхүүр нь a^b%m гэсэн томъёогоор гарах тоо байхыг хүмүүс олж чаджээ. Энд % нь бүхлээр хувааж үлдэгдлийг олох үйлдэл юм.

Таны хувьд түлхүүр тоог хангалттай хурдан тооцоолох програм бичих үүрэг оногдож байна.

Input

Эхний мөрөнд тестийн тоо t өгөгдөнө (2<=t<=40000).

Дараагийн t ширхэг мөр тус бүрт a, b, m тоонууд хоосон зайгаар тусгаарлагдан өгөгдөнө (2<=a<=10⁶, 2<=b<=10⁶, 2<=c<=10⁶).

Output

Тест бүрийн хувьд түлхүүр тоог нэг нэг мөрөнд хэвлэнэ.

Example

Input:
3
2 10 10
123456 654321 999999

1000000 999998 999996

Output:
4
986175

436528