gladiator2001
Badges: 2
Rep:
?
#1
Report Thread starter 6 months ago
#1
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
0
reply
sowji
Badges: 3
Rep:
?
#2
Report 5 months ago
#2
please send answer
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of East Anglia
    PGCE Open day Postgraduate
    Tue, 3 Mar '20
  • University of Bradford
    Postgraduate Open day/Evening Postgraduate
    Tue, 3 Mar '20
  • Queen's University Belfast
    Postgraduate LIVE Masters & PhD Study Fair Postgraduate
    Wed, 4 Mar '20

Do you get study leave?

Yes- I like it (506)
59.67%
Yes- I don't like it (43)
5.07%
No- I want it (241)
28.42%
No- I don't want it (58)
6.84%

Watched Threads

View All