The chef was busy in solving algebra, he found some interesting results, that there are many numbers which can be formed by the sum of the factorial of the digits, he wrote all those interesting numbers in the diary(in increasing order) and went to sleep. Cheffina came and stole his diary, in morning chef found that his diary is missing. Now the chef wants your help to find those numbers, Chef asks you whether N is that interesting number or not. If N is an interesting number then print 1. Else print 0. 

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, $N$. 

-----Output:-----
For each test case, output in a single line answer 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $0 \leq N \leq 10^9$

-----Sample Input:-----
2
2
10

-----Sample Output:-----
1
0

-----EXPLANATION:-----
For 1) Factorial of 2 is 2, hence it is an interesting number.
For 2) conversion for 10 is 1! + 0! = 2, which is not equal to 10, hence not an interesting number.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for i in range(t):
    n = int(input())
    if n == 1 or n == 2 or n == 145 or n == 40585:
        print(1)
    else:
        print(0)


from collections import Counter
import string
import math
import sys
# sys.setrecursionlimit(10**6) 
def isprime(x): 
      
    # check for numbers from 2 
    # to sqrt(x) if it is divisible 
    # return false 
    i = 2
    while(i * i <= x): 
        if (x % i == 0): 
            return 0
        i+=1
    return 1
def isSumOfKprimes(N, K): 
      
    # N < 2K directly return false 
    if (N < 2 * K): 
        return 0
  
    # If K = 1 return value depends 
    # on primality of N 
    if (K == 1): 
        return isprime(N) 
  
    if (K == 2): 
          
        # if N is even directly 
        # return true; 
        if (N % 2 == 0): 
            return 1
  
        # If N is odd, then one  
        # prime must be 2. All  
        # other primes are odd 
        # and cannot have a pair 
        # sum as even. 
        return isprime(N - 2)
      
  
    # If K >= 3 return true; 
    return 1
from fractions import Fraction
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(arrber_of_variables):
    if arrber_of_variables==1:
        return int(sys.stdin.readline())
    if arrber_of_variables>=2:
        return list(map(int,sys.stdin.readline().split())) 
def makedict(var):
    return dict(Counter(var))
testcases=vary(1)
fact=[1 for i in range(11)]
for i in range(1,10):
    fact[i]=fact[i-1]*i
for _ in range(testcases):
    n=vary(1)
    p=n
    ans=0
    if n==0:
        print(0)
        continue
    while n>0:
        x=n%10
        ans+=fact[x]
        n//=10
    if p==ans:
        print(1)
    else:
        print(0)
    
        

    
    


# cook your dish here
n=int(input())
l=[1,2,145,40585]
for i in range(n):
    t=int(input())
    if t in l:
        print(1) 
    else:
        print(0)

# cook your dish here
a=[1]
fact=[1]
for i in range(1,15):
    fact.append(fact[i-1]*i)
for i in range(int(input())):
    n=int(input())
    if n in [1,2,1,145,40585]:
        print(1)
    else:
        print(0)


# cook your dish here
for _ in range(int(input())):
    n = int(input())
    if n==1 or n==2 or n==145 or n==40585:
        print(1)
    else:
        print(0)

# cook your dish here
import sys
T=int(input())
fact=[1,1,2,6,24,120,720,5040,40320,362880]
for t in range(T):
    N=sys.stdin.readline().strip()
    cnt=0
    for n in N:
        cnt+=fact[int(n)]
    if str(cnt)==N:
        print(1)
    else:
        print(0)




p = [1,2,145,40585]
for _ in range(int(input())):
    N = int(input())
    if N in p:
        print(1)
    else:
        print(0)