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.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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

def isprime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return 0
		i += 1
	return 1

def isSumOfKprimes(N, K):
	if N < 2 * K:
		return 0
	if K == 1:
		return isprime(N)
	if K == 2:
		if N % 2 == 0:
			return 1
		return isprime(N - 2)
	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)


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)


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)


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)