Cho một số \(n\), tìm hiểu xem số này có phải là số Smith hay không. Số Smith là số không nguyên tố và có tổng các chữ số của nó bằng tổng các chữ số của các thừa số nguyên tố của nó trong dãy phân tích thừa số nguyên tố. Ví dụ:

• \(n = 4\), tổng các chữ số bằng 4, \(n\) = 4 = 2 x 2 và 2 + 2 = 4. Do đó , 4 là số Smith
• \(n = 6\), có tổng các chữ số bằng 6, \(n\) = 6 = 2 x 3 và 2 + 3 = 5 khác với 6. Do đó, 6 không phải là số Smith
• \(n = 666\), có tổng các chữ số bằng 18, \(n\) = 666 = 2 x 3 x 3 x 37 và 2 + 3 + 3 + (3 + 7) = 18. Do đó, 666 là một số Smith
• \(n = 13\), có tổng các chữ số bằng 4, n = 13 có một ước là 13 và có tổng các chữ số của ước cũng là 4 nhưng vì 13 là số nguyên tố nên 13 không phải là số Smith.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) là số bộ dữ liệu vào kiểm tra, mỗi bộ dữ liệu vào gồm một dòng chứa một số nguyên dương \(n\).

Ràng buộc:

• \(0 < T \leq 200; 0 < n \leq 10^9.\)

Kết quả

• in ra \(T\) dòng, mỗi dòng in ra số 1 nếu \(n\) là số Smith, ngược lại thì in ra 0.

Ví dụ:

INPUT

4
4
6
666
13

OUTPUT

1
0
1
0