Non-squares

Given a positive integer n, determine if it can be expressed as the product of k positive integers, where none of these integers is a perfect square.

Input

The first line of input contains an integer t (1 ≤ t ≤ 10) - the number of test cases. Each of the following t lines contains one test case, consisting of two integers n (1 ≤ n ≤ 1000000000) and k (2 ≤ k ≤ 50).

Output

For each test case, output "YES" on a separate line if there exists a set of k positive integers a_i such that n = a_1·a_2·...·a_k and none of the a_i is a perfect square. Otherwise, output "NO".

Examples