Babu and Sabu are enemies but they fight with each other with the help of the mind games not guns. One day Babu asks Sabu to give the answer for this mathematical query as following:

Let f(m, n) = m^n

But Sabu is little weak in mathematics and he wants the help to answer the question.

Your aim is to answer f(m1, n1)^f(m2,n2) % n

Can you help Sabu to give answer of question to Babu.

INPUT:

You are given T which is the number of queries to solve.

Each Query consist of 5 space separated integers m1, n1, m2, n2, n.

OUTPUT:

Output contains exactly T lines. i th line containing the answer for the i th query.

Constraints:

1 <= T <= 10000

0 <= m1, n1, m2, n2, n <= 1000000000

1 <= n <= 10000000