You are given a sequence $A_{1},A_{2},…,A_{n}$. Determine the count of integers $z$ ($z\in A$) that satisfies the following property $:$

$\prod_{i=1}^{z-1}\thinspace i\enspace mod\thinspace z = z-1$

Note: Your program must solve $T$ independent test cases.

Input format

• First line: $T$ denoting the number of test cases
• For each test case:
  • First line: $n$ denoting the size of the sequence
  • Second line: $n$ numbers $A_1, A_2, ..., A_n$ denoting the elements in the sequence

Output format

For each test case, print a number that indicates the count of integers in the sequence that satisfies the property. The output must be printed in a single line.

Constraints

$1 \leq T \leq 10$

$1 \leq n \leq 10^5$

$2 \leq A_i \leq 10^8$

Note: To know more about the $\prod$ notation, read Capital_pi_notation.