Sanae's Ghost Band Performance Rating

Kochiya Sanae is a big fan of the Ghost Band and wants to rate their performance. The band consists of 3 members, so their performance score is represented by three positive integers A, B and C. The overall score is defined as:

$$ S = \prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\mathrm{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)} $$

where the function \(f(\cdot)\) is defined for three different modes type as follows:

$$ \begin{aligned} f(0)&=1,\\ f(1)&= i \times j \times k,\\ f(2)&=\gcd(i,j,k). \end{aligned} $$

Since the score can be enormous, it is computed modulo a given positive integer p.

You are given T queries. Each query provides values for A, B, C, type and p. For each query, compute the overall score S modulo p.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 10) representing the number of queries. Each of the following T lines contains five positive integers: A, B, C, type (which is 0, 1, or 2), and p (modulus).

It is guaranteed that A, B, C are small enough to allow a triple nested loop solution.

outputFormat

For each query, output a single line containing the performance score modulo p.

sample

1
1 1 1 0 1000

1