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.