C. Count the numbers if you can!

5

2 votes
Mathematics, Algorithms, Number theory
Problem

Saurabh loves numbers a lot. He has a board which has all the infinitely many natural numbers written on it. (The board is big enough to contain all the infinitely many natural numbers that can possibly exist!!)

Deepjoy (one of his mischievous friends) tries to manipulate the numbers written on the board using a magic function F(x) and a set S.

The details of the magic function and the set are given below:

  • The set S contains n elements.
  • Fk(x)=x for all k belonging to the set S.
  • x belongs to the set of natural numbers.
  • All elements of the set S satisfy the magic function. (i.e. Fm(x)=x, where m is any natural number in the set S)

Here Fk(x)=F(F(F(..F(x)))), where F is repeated k times.

Now Deepjoy gives the magic function F(x) and a set S containing n elements to Saurabh and asks him to rub all the numbers m which satisfy the magic function (i.e. Fm(x)=x, where m is any natural number). Now he asks Saurabh to count the remaining numbers left on the board!

Saurabh is confused whether he would be able to count the remaining numbers left on the board or not. (remember infinitely many natural numbers were written on the board)!

Help him to count the numbers that are left on the board (if you can)!

 

Input: 

  • First line: A single integer T denoting the number of test cases
  • Each test case contains the following lines:
    • 1st line: N, the no. of elements in the set S
    • N lines follow denoting the elements of the set S

Output:

Print "Yes, I can" if the no. of remaining elements are countable (finite no. of elements are left on the board) otherwise print "No, I can't" in a single line. (ignore the quotes while printing the answer)

Constraints:

1T103

1N103

1 Elements in the set S31018

Sample Input
2
2
1
2
1
2
Sample Output
Yes! I can
No! I can't
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

1st test case:

1 belongs to the set S={1,2}. So, F(x)=x is true for all natural numbers x.

Now F2(x)=F(F(x))=F(x)=x, this shows that magic function is true for m=2. Similarly we can show that Fm(x)=x is true for all natural numbers m.

Therefore the answer is "Yes, I can".

Editor Image

?