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.