Greetings to all of you. You must have heard about our star programmer Rafat bhai. One day he went on a date with his girlfriend and he was discussing his recent IUPC contest details.

One of the question caught her attention she thought she could solve it but Rafat bhai knows it's too hard for her so he decided to modify it a bit. The task is simple, check whether the sum of divisors of N is a prime or not. But it's still to hard for her but she wants to complete it so she needs a bit of help from you.

You the rising star, can you help her by solving this problem? She promised to give you a treat if you can solve it.

Input

You will be given an integer T (1 ≤ T ≤ 22) in the first line. In next T lines there will be an integer N (1 ≤ N ≤ 107).

Output

In each case, print "Yes" if the sum of divisors of N is a prime otherwise "No" without quotes.