http://codeforces.com/problemset/problem/984/C

Time limit    1000 ms
Memory limit    262144 kB

题目

You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.

A fraction in notation with base $b$ is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.

Input

The first line contains a single integer $n$ ($1\leqslant n \leqslant 10^5$) — the number of queries.

Next