Count Zeros in Each Record

Source: Phước Hưng OJ

Problem Statement

There are t records; record i contains one nonnegative integer a_i. For EACH integer separately, count how many digit 0 characters appear in its ordinary decimal representation, which has no leading zeros. The number 0 is represented by the single digit 0, so its answer is 1. Output results in input order.

Input

The first line contains the integer t. The following input contains exactly t integers a_1,...,a_t, separated by whitespace; line breaks between them are insignificant. All integers are nonnegative.

Output

Print exactly t lines. Line i contains one integer: the number of digit 0 characters in a_i. Print no labels or extra characters.

Subtasks

• Subtask 1 (20%): 1 <= t <= 5 and 0 <= a_i <= 1000.
• Subtask 2 (30%): 1 <= t <= 100 and 0 <= a_i <= 10^6.
• Subtask 3 (50%): 1 <= t <= 1000 and 0 <= a_i <= 10^9.

Examples

Example 1

Input:

5
0 10 1005 909 123

Output:

1
1
2
1
0

Explanation:

The representations are 0, 10, 1005, 909 and 123. The value 1005 has two zeros; the number 0 itself has one zero.

Example 2

Input:

3
1000000000
10101
7

Output:

9
2
0

Explanation:

10^9 is a 1 followed by nine zeros; 10101 contains two zeros.