Just Solve It

You are given an array $A$ of length $N$ consisting of integer numbers. Your task is to determine the value returned by following “Solve()” function.

var Solve(var N,var A[]) {
  var count=0;
  for(var i=1; i<=N; i++) {
    for(var j=i+1; j<=N; j++) {
      var product=A[i]*A[j];
      if( LSD(product) == 0 ) {
        count++;
      }
    }
  }
  return count;
}

Here, Least Significant Digit (LSD) refers to the digit which occurs rightmost in its decimal representation.

Input

Input starts with an integer $T$ ($1 \le T \le 20$), denoting the number of test cases. Each case contains an integer $N$ ($1 ≤ N ≤ 100000$) denoting the number of elements of array $A$. The next line will contain $N$ nonnegative integers not greater than $10^{12}$ separated by a space, denoting the elements of the array.

Output

For each case of input, output the result of above function as described in the problem statement.

Sample

Input	Output
1 4 1 2 3 5	1