eolymp
bolt
Try our new interface for solving problems
Problems

Неквадраты

Неквадраты

Time limit 2 seconds
Memory limit 512 MiB

Задано целое положительное число n.

Выясните, может ли оно быть представлено в виде произведения k целых положительных чисел, ни одно из которых не является квадратом целого числа.

Input data

Первая строка ввода содержит целое число t (1t10) - количество тестовых случаев. Каждая из последующихt строк содержит один тестовый случай, состоящий из двух целых чисел n (1n1000000000) и k (2k50).

Output data

Для каждого тестового случая выведите в отдельной строке слово "YES" в том случае, если существует такой набор из k положительных целых чисел a_i, что n = a_1·a_2·...·a_k и ни одно из a_i не является квадратом целого числа, и слово "NO" в противном случае.

Examples

Input example #1
4
1 2
6 2
7 2
8 3
Output example #1
NO
YES
NO
YES
Source Yandex.Algorithm, Online Round 1, July 14, 2013