Cho một số nguyên trong hệ nhị phân. Xác định xem số nguyên này có chia hết cho \(15\) hay không.

Input

• Dòng đầu tiên là \(t\) số lượng bộ test
• \(t\) dòng tiếp theo mỗi dòng là 1 chuỗi nhị phân

Output

• Mỗi dòng ghi kết quả là 1 nếu chia hết, 0 nếu không chia hết

Example

Sample input

3
1111
1100
11110

Sample output

1
0
1