Yêu cầu

Một số nguyên dương \(n\) được gọi là số đặc biệt nếu \(n\) chia hết cho tổng các chữ số của \(n\). Ví dụ, số 27 là số đặc biệt vì \(27\) chia hết cho \(2+7=9\), còn hai số \(11\) và \(2021\) thì không phải là số đặc biệt.

Input

• Dòng 1 ghi số \(t\) là số test (\(0 < t \le 100\))
• \(t\) dòng kế tiếp mỗi dòng chứa duy nhất \(n\) (\(0≤ \le n \le 10^{18}\)).

Output

• In ra \(t\) dòng, mỗi dòng ghi 1 nếu số đó là đặc biệt, ghi 0 nếu ngược lại.

Ví dụ

input

    3 
    11
    22
    27

output

0
0
1