Chef has a number N, Cheffina challenges the chef to check the divisibility of all the permutation of N by 5. If any of the permutations is divisible by 5 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$
- $1 \leq N \leq 10^6$

-----Sample Input:-----
2
19
385

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

Difficulty: interview

Starter code:

Solutions:
a = int(input())
for i in range(a):
	b = input()
	if '5' in b or '0' in b:
		print(1)
		continue
	print(0)

t=int(input())
while(t):
    n=input()
    if('0' in n or '5' in n):
        print('1')
    else:
        print('0')
    t=t-1

t=int(input())
for t1 in range(t):
	n=input()
	a=0
	for i in n:
		if i=='0' or i=='5':
			a=1
			break
			
	print(a)

from sys import *
input=stdin.readline
for i in range(int(input())):
    n = int(input())
    while n > 0:
        r = n%10
        if r%5 == 0:
            print(1)
            break
        n = n // 10
    else:
        print(0)


T=int(input())

for _ in range(T):
    
    N=input()
    if '0' in N or'5' in N:
        print(1)
    else:
        print(0)

from sys import*
input=stdin.readline
t=int(input())
for _ in range(t):
    s=list(input())
    n=s.count('0')+s.count('5')
    if n>0:
        print('1')
    else:
        print('0')


t=int(input())
for i in range(t):
    a=input()
    if '0' in a: 
        print('1')
    elif '5' in a:
        print('1')
    else:
        print('0')


t=int(input())
for i in range(t):
    a=input()
    if '0' in a: 
        print('1')
    elif '5' in a:
        print('1')
    else:
        print('0')

t=int(input())
for i in range(t):
    a=input()
    if '0' in a: 
        print('1')
    elif '5' in a:
        print('1')
    else:
        print('0')

# cook your dish here
for i in range(int(input())):
    n=int(input())
    n=str(n)
    z=n.find('5')
    z1=n.find('0')
    if(z==-1 and z1==-1):
        print('0')
    else:
        print('1')


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

# cook your dish here
n=int(input())
ls=[]
for _ in range(n):
    ls.append(int(input()))
for ele in ls:
    ele=str(ele)
    ele=list(ele)
    flag=0
    for i in ele:
        if(int(i)%5==0):
            print("1")
            flag=1
            break
    if flag==0:
        print("0")
        


def f(n):
    string = str(n)
    for char in string:
        if char in '05':
            return 1
    return 0

t = int(input())
answers = list()
for _ in range(t):
    n = int(input())
    answers.append(f(n))

for answer in answers:
    print(answer)

for _ in range(int(input())):
    n=int(input())
    a=str(n)
    if(a.count('0') or a.count('5')):
        print('1')
    else:
        print('0')


# cook your dish here


for _ in range(int(input())):
    n=input()
    flag=0
    for i in n:
        if i=="0" or i=='5':
            flag=1
            break
    if flag==0:
        print('0')
    else:
        print("1")

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n=input()
    for i in range(len(n)):
        if(n[i]=='0' or n[i]=='5'):
            print("1")
            break
    else:
        print("0")

for _ in range(int(input())):
    l = list(input())
    if "0" in l or "5" in l:
        print(1)
    else:
        print(0)

for _ in range(int(input())):
    N = input()
    if '5' in N or '0' in N:
        print(1)
    else:
        print(0)

t=int(input())
while(t>0):
    n=input()
    if(('5' in n) or ('0' in n)):
        print(1)
    else:
        print(0)
    t-=1
# cook your dish here


# cook your dish here
for i in range(int(input())):
    num=input()
    if '5' in num or '0' in num:
        print(1)
    else:
        print(0)


def func(num):
    for x in num:
        if x == '0' or x == '5':
            print(1)
            return
    print(0)


for _ in range(int(input())):
    num = input()
    func(num)


t=int(input())
for i in range(t):
    n=input()
    if("0" in n or "5"in n):
        print(1)
    else:
        print(0)

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
inp = lambda: list(map(int,sys.stdin.readline().rstrip("\r\n").split()))
#______________________________________________________________________________________________________
# from math import *
# from bisect import *
# from heapq import *
# from collections import defaultdict as dd
# from collections import OrderedDict as odict
# from collections import Counter as cc
# from collections import deque
# sys.setrecursionlimit(2*(10**5)+100) this is must for dfs
# mod = 10**9+7; md = 998244353
# ______________________________________________________________________________________________________
# segment tree for range minimum query
# sys.setrecursionlimit(10**5)
# n = int(input())
# a = list(map(int,input().split()))
# st = [float('inf') for i in range(4*len(a))]
# def build(a,ind,start,end):
#   if start == end:
#       st[ind] = a[start]
#   else:
#       mid = (start+end)//2
#       build(a,2*ind+1,start,mid)
#       build(a,2*ind+2,mid+1,end)
#       st[ind] = min(st[2*ind+1],st[2*ind+2])
# build(a,0,0,n-1)
# def query(ind,l,r,start,end):
#   if start>r or end<l:
#       return float('inf')
#   if l<=start<=end<=r:
#       return st[ind]
#   mid = (start+end)//2
#   return min(query(2*ind+1,l,r,start,mid),query(2*ind+2,l,r,mid+1,end))
# ______________________________________________________________________________________________________
# Checking prime in O(root(N))
# def isprime(n):
#     if (n % 2 == 0 and n > 2) or n == 1: return 0
#     else:
#         s = int(n**(0.5)) + 1
#         for i in range(3, s, 2):
#             if n % i == 0:
#                 return 0
#         return 1
# def lcm(a,b):
#   return (a*b)//gcd(a,b)
# ______________________________________________________________________________________________________
# nCr under mod
# def C(n,r,mod):
#   if r>n:
#       return 0
#   num = den = 1
#   for i in range(r):
#       num = (num*(n-i))%mod
#       den = (den*(i+1))%mod
#   return (num*pow(den,mod-2,mod))%mod
# M = 10**5 +10
# ______________________________________________________________________________________________________
# For smallest prime factor of a number
# M = 1000010
# pfc = [i for i in range(M)]
# def pfcs(M):
#   for i in range(2,M):
#       if pfc[i]==i:
#           for j in range(i+i,M,i):
#               if pfc[j]==j:
#                   pfc[j] = i
#   return
# pfcs(M)
# ______________________________________________________________________________________________________
tc = 1
tc, = inp()
# a = [0,1]
# for i in range(100000):
#     a.append(a[-1]+a[-2])
for _ in range(tc):
    n, = inp()
    print(1 if any([int(i)%5==0 for i in str(n)]) else 0)