"Riddle me this, Batman."

The Riddler has taken Gotham City hostage and it is up to Batman to save his city.

Batman has been given a very large number of puzzles by the Riddler to solve. If Batman solves these puzzles, he gets the Riddler's exact location, which should allow him to save the city from another Zero Year scenario.

The puzzles that Batman has to solve are all of the same type:

Given a number n, check if n has exactly k distinct prime factors.

Input:

The first line of each test case contains the number of puzzles (t).

Each test case consists of a single line containing n and k.

Output:

For each test case, print "YES" if n has exactly k distinct prime factors else print "NO".

Constraints:

1 <= t <= 1000000 (1e6)

2 <= n <= 1000000

1 <= k <= 1000000