CF1538D Another Problem About Dividing Numbers

You are given two integers $ a $ and $ b $ . In one turn, you can do one of the following operations: - Take an integer $ c $ ( $ c > 1 $ and $ a $ should be divisible by $ c $ ) and replace $ a $ with $ \frac{a}{c} $ ; - Take an integer $ c $ ( $ c > 1 $ and $ b $ should be divisible by $ c $ ) and replace $ b $ with $ \frac{b}{c} $ . Your goal is to make $ a $ equal to $ b $ using exactly $ k $ turns. For example, the numbers $ a=36 $ and $ b=48 $ can be made equal in $ 4 $ moves: - $ c=6 $ , divide $ b $ by $ c $ $ \Rightarrow $ $ a=36 $ , $ b=8 $ ; - $ c=2 $ , divide $ a $ by $ c $ $ \Rightarrow $ $ a=18 $ , $ b=8 $ ; - $ c=9 $ , divide $ a $ by $ c $ $ \Rightarrow $ $ a=2 $ , $ b=8 $ ; - $ c=4 $ , divide $ b $ by $ c $ $ \Rightarrow $ $ a=2 $ , $ b=2 $ . For the given numbers $ a $ and $ b $ , determine whether it is possible to make them equal using exactly $ k $ turns.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ). Then $ t $ test cases follow. Each test case is contains three integers $ a $ , $ b $ and $ k $ ( $ 1 \le a, b, k \le 10^9 $ ).

For each test case output: - "Yes", if it is possible to make the numbers $ a $ and $ b $ equal in exactly $ k $ turns; - "No" otherwise. The strings "Yes" and "No" can be output in any case.