A number is called strong number if the sum of the factorial of its digit is equal to number itself. For example: 145 since

    1! + 4! + 5! = 1 + 24 + 120 = 145

So, 145 is a strong number. Now given a positive number N and you have to find whether the number is strong number or not.

Input

An integer T (1 <= T <= 1000) denoting the number of test cases followed by T lines. Each containing a single integer N (0 <= N <= 10¹⁸)

Output

For each case output string “YES” if given number is strong number and “NO” otherwise.

Example

Input:
2
145
12

Output:
YES
NO

Problem Setter: Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)