Alice goes for a walk and notices \(N\) cakes where the \(i^{th}\) cake has value \(v_{i}\). Alice's initial \(happiness = 1\). Eating a cake of value \(X\) multiplies her \(happiness\) by a factor of \(X\). However, she finds two prime numbers peculiar \(A, B\). She will be very sad if her \(happiness\) is a multiple of both \(A\) and \(B\). What is the maximum number of cakes which she can eat?

Input Format

First-line has \(T\) indicating number of test cases.

Each test case is printed on a new line:

\(NABv_{1}..v_{N}\)

Output Format

Print answer for each test case on a new line.

Constraints