Our social:

Amazon SDE Hiring Challenge Problem : Milly and equal array Answer (solution)

Milly is playing with a Array A of size N. She wants to make all the values of A to be equal. She can multiply any value any number of times by XY and Z. Your task is to tell her whether she can do it or not. Print "She can" if she can do it else print "She can't" without "".

Input

  • First line of the input will contain T (No. of test cases).
  • For each test case, first line will contain four space separated integers denoting NXY and Z. Then next line will contain N space separated integers of A

Output

  • For every test case, print the required answer in a new line.

Constraints

  • 1 ≤ T ≤ 5
  • 2 ≤ N ≤ 105
  • X, Y, Z ∈ {2, 3, 5, 7}
  • 1 ≤ Ai ≤ 109


Sample Input
(Plaintext Link)

2
2 2 2 2
2 4
3 2 3 2
2 6 7

Sample Output
(Plaintext Link)

She can
She can't




Image result for amazon




Explanation
Test case #1: Multiply first value by 2.
Test case #2: Not possible.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded if any testcase passes.
Allowed languages: C, C++, Clojure, C#, Go, Haskell, Java, JavaScript(Rhino), Objective-C, Perl, PHP, Python, Ruby


                              ANSWER HERE