Max pow

Given three integer X , Y and Z. Find maximum value of p such that Z p divides factorial of (X*Y). Input Input will begin with an integer T (at most 100), the number of test cases. T testcases follow, each having three space seprated integer X, Y, Z (2 ≤ Z ≤ 109 , 2 ≤ Y ≤ 109, 2 ≤ Z ≤ 1012 ). Output For each test case, output maximum value of p. Example Input: 2 2 2 24 5 2 10 Output: 1 2