One day Patrik met a magician.He asked magician for his magic pencil.So magician decided to give him magic pencil only if he correctely answers to his question. Magician gave him 3 numbers a, b and c and asked him to find the multiple of c which is closest to a^b.Help patrik to solve this problem and win magic pencil.

Note:If more than one answer is possible , print the smallest one.

Input Format:

The first line contains T, the number of testcases. T lines follow, each line contains 3 space separated integers a, b and c respectively.

Output Format:

For each test case , print the multiple of c which is closest to a^b

Constraints:

1 ≤ T ≤ 10^5

1 ≤ a ≤ 10^9

-10^9 ≤ b ≤ 10^9

1 ≤ c ≤ 10^9

0 < a^b ≤ 10^9