solve a coding problem in c++ language

gladiator2001

In the Prodigy classes, the mathematics teacher has suddenly fallen ill. The class is very important so Jeetu Bhaiya has decided to take the class. Although, he is the best physics teacher in the kota, he decided to take the Mathematics class for a change and also because of the students demand. Jeetu Bhaiya always teach in a different and interesting manner, who can forget the rim experiment. This time too he has decided to bring something interesting to the table.

He has brought a few dummies with numbers on them to demonstrate a problem. He goes on to explain the problem to the students.

The dummies are divided into two groups and the product of the respective groups is calculated. Out of the different groups, only the groups whose product gcd is 1 are to be picked.

1. Group 1: {2, 3}; Product = 6

Group 2: {5}

gcd(6, 5) = 1
The problem is to find the number of ways of dividing the dummies into groups such that the gcd of their product is 1. For the given set of dummies, there are 6 ways of dividing them into two groups following the property.

2. Group 1: {2}

Group 2: {3, 5}

. Group 1: {2, 5}

Group 2: {3}

4. Group 1: {3}

Group 2: {2, 5}

. Group 1: {2, 5}

Group 2: {3}

4. Group 1: {3}

Group 2: {2, 5}

3. Group 1: {2, 5}

Group 2: {3}

4. Group 1: {3}

Group 2: {2, 5}

5. Group 1: {3, 5}

Group 2: {2}

6. Group 1: {5}

Group 2: {2, 3}

Note: The two groups cannot be empty. Since, the output can be very large print it modulo 10^9+7. Also, remember the two groups are different which should be clear from sample test cases and the demonstration. This information is provided by Jeetu Bhaiya.

Input Format
The first line of input consists of the number of test cases, T.

The first line of each test case consists of the number of dummies, N.

The second line of each test case consists of the N space separated positive integers in the list.

Constraints
1<= T <=5

1<= N <=10^5

1<= Di <=10^6

Output Format
For each test case, print the number of ways of dividing groups in separate lines.

Sample TestCase 1
Input
Input
2
3
2 3 4
4
2 4 6 8
Output
2
0Explanation

Test Case 1: There are two ways in which the dummies can be divided into two groups following the property.

Group 1 : {2, 4}; Group 2 : {3}

Group 1 : {3}; Group 2 : {2, 4}

Test Case 2: It is not possible to divide the dummies into two groups following the property.

Time Limit(X):
1.50 sec(s) for each input.
Memory Limit:
512 MB
Source Limit:
100 KB
Allowed Languages:
C, C++, C++11, C++14, C#, Java, Java 8, Kotlin, PHP, PHP 7, Python, Python 3, Perl, Ruby, Node Js, Scala, Clojure, Haskell, Lua, Erlang, Swift, VBnet, Js, Objc, Pascal, Go, F#, D, Groovy, Tcl, Ocaml, Smalltalk, Cobol, Racket, Bash, GNU Octave, Rust, Common LISP, R, Julia, Fortran, Ada, Prolog, Icon, Elixir, CoffeeScript, Brain****, Pypy, Lolcode, Nim, Picolisp, Pike, pypy3

please answer fast

solve a coding problem in c++ language

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you