Little Fahad has found some numbers. Now he wants to multiply the numbers. But after the operation he can see the number is a very big one. Then he counts out the number of trailing zeros of the number. Again he has found some numbers and this time he doesn’t want to do all the operations he did before by himself. As you are a very good friend of Fahad and also a very good programmer, help him by writing a program that will calculate the number of trailing zeros of the number formed by the numbers after multiplying them together.

Input

Input starts with T (1 <= T <= 100) denoting the test case. Every test case will contain a number n (1 <= n <= 10⁶) the number of numbers Fahad has found. Then there will be n integers a_i (1 <= a_i <= 10⁶).

Output

Output a single integer the number of trailing zeros.

Example

Input:
2
3
1 2 5
5
5 5 3 4 10

Output:
1
3

Problem Setter: Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)