Много степеней по модулю

Дано $q$ запросов. В каждом три числа: $a$, $b$ и $m$. Выведите остаток от деления $a^b$ на $m$.

В первой строке число $q$ от $1$ до $100$. В следующих $q$ строках по три числа: $a$ от $0$ до $10^9$, $b$ от $0$ до $10^{18}$ и $m$ от $1$ до $10^9$.

Числа через пробел.