Biutiful Number

Lately, Christo's mind is preoccupied with a certain kind of number; up to the point where he used his ID card to withdraw money from an ATM. What Christo interested in is integers which are the sum of arithmetic sequences with the first term being 1 and the difference between adjacent terms is 1. For Christo, such numbers are biutiful.

For example:

On the other hand, numbers such as 2, 4, and 40 are not biutiful as they are not the sum of any arithmetic sequence with the first term of 1 and difference of 1.

Given an integer, determine whether it is biutiful.

Input

Input begins with an integer: T (1 ≤ T ≤ 100) denoting the number of cases. Each case contains a single line with an integer: N (1 ≤ N ≤ 1,000,000) denoting the given integer.

Output

For each case, output in a line "Case #X: Y" where X is the case number (starts from 1) and Y is "YES" (without quote) if the given input is biutiful, otherwise Y is "NO" (without quotes).

Examples

inputExample #1
4
3
2
21
1000
output
Case #1: YES
Case #2: NO
Case #3: YES
Case #4: NO
explanation

Case 1: 3 = 1 + 2

Case 3: 21 = 1 + 2 + 3 + 4 + 5 + 6



End of Problem