LCM^k

Given three integers N,M,K and array of integers a₁,a₂,...,a_n.
Find the value of LCM(a₁^k,a₂^k,...,a_n^k) mod M, where LCM means Least Common Multiple.

Input

The first line of the input contains a single integer T denoting the number of test cases(1 ≤ T ≤ 10). 
The description of T test cases follows.
First line contains three positive integers N, M, K(1 ≤ N ≤ 3 * 10⁵, 1 ≤ M, K ≤ 10⁹).
The second line contains N space-separated integers a₁,a₂,...,a_n.(1 ≤ a_i ≤ 10⁶,1 ≤ i ≤ N).

Output
For each test case print the value of LCM(a₁^k,a₂^k,...,a_n^k) mod M.

SAMPLE INPUT

 

1
5 20 3
17 2 9 4 12

SAMPLE OUTPUT

 

8

Explanation

In the test LCM(17³,2³,9³,4³,12³) = 229220928, 229220928 mod 20 = 8.

Note:- Time Extended Problem Occur