NUMBERG - Number Game

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 <= 106) the number of numbers Fahad has found. Then there will be n integers ai (1 <= ai <= 106).

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)


Added by:Shipu Ahamed
Date:2013-06-29
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.