Let, BLCM(a,b) be the smallest positive integer which is divisible by all integers in range [a,b].
Given 3 positive integers a, b and c, find an integer n for which BLCM(a,b) is divisible by cn. If there are more than one possible n, find the largest one.
Input
Input starts with an integer T (0<T≤100) denoting number of test cases.
The next T lines each contains three integers a, b, c (0<a≤b≤1018 and 1<c≤1018).
Output
For each test case, print an integer in one line containing your answer to that test case.