C. Chữ số 0 tận cùng
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Huy được Bảo giao một bài toán sau:

Cho một dãy gồm $$$n$$$ con số $$$a_1, a_2, \ldots, a_n$$$. Gọi $$$P$$$ là kết quả sau khi nhân các con số trong dãy trên lại với nhau. Hãy tìm số chữ số $$$0$$$ ở tận cùng của $$$P$$$.

Huy thấy bài toán trên là quá khó, các bạn hãy giúp Huy.

Biết rằng số chữ số $$$0$$$ tận cùng của $$$x$$$ là số $$$k$$$ ($$$k \ge 0$$$) lớn nhất mà $$$y \times 10^k = x$$$.

Input

Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcase.

Dòng đầu tiên của mỗi testcase là một số nguyên $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số phần tử trong dãy.

Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên dương $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) $$$-$$$ các phần tử trong dãy.

Output

Với mỗi testcase, trên một dòng, in ra số chữ số $$$0$$$ tận cùng của $$$P$$$.

Example
Input
3
5
4 5 7 1 6
2
1000 10000
1
1
Output
1
7
0
Note

Ở ví dụ đầu tiên, $$$840 = 4 \times 5 \times 6 \times 7 \times 1$$$, có một chữ số $$$0$$$ tận cùng.

Ở ví dụ thứ hai, $$$1000000 = 1000 \times 10000$$$, có bảy chữ số $$$0$$$ tận cùng.

Ở ví dụ thứ ba, $$$1$$$ không có chữ số $$$0$$$ tận cùng nào.