NITT2 - hai jolly jolly jolly

no tags 

Alp and Gaut are like always opposite to each other. Once Alp told that he can identify a number which is divisible by 252 (He knows because that is his girlfriends birthday - 25/2). Now to come up against Alp, Gaut said he can identify whether the number is divisible by 525 (poor Gaut don't have a girl friend though). The truth is they don't know to do it for big numbers. So you are here to help them with a method. Given a number you have to tell whether the number is divisible by 252 and 525.

Input

Number of testcases in first line, T (T <= 100).

Each line contains one number N, whose divisibility is to be tested (1 <= N <= 1050000).

Output

Each line containing two Yes/No. one for 252 and one for 525.

Example

Input:
4
252
525
16884
21347

Output:
Yes No
No Yes
Yes No
No No

hide comments
anuj0503: 2016-06-17 14:02:06

A number is divisible by a composite number iff it is divisible by the highest power of each of its prime factors e.g., we can check for divisibility by 252 (252=2^2*3^2*7) by checking for divisibility by 4, 9 and 7

Last edit: 2016-06-17 14:02:35
ragwave: 2016-05-22 14:58:37

well the question can be done without using divisibility tests!!

minhthai: 2016-01-28 16:37:23

dont bruteforce :)

shantanu tripathi: 2015-08-13 21:35:57

should be moved to tutorials...

i_am_looser: 2015-05-27 21:16:46

easy ;)

Last edit: 2015-05-27 21:17:02
Vaporeon: 2015-05-23 23:09:04

TLE in python 2.7.9.. AC in PYPY :P

thelazycoder: 2015-02-15 22:32:46

how to store 10^50000

Last edit: 2015-02-15 22:33:38
Rajat (1307086): 2015-01-20 03:19:52

nostalgic!!!
had to go through class 3 notes to revise divisibility tests.
;)

Ranjan Kumar Singh: 2015-01-20 03:19:52

time limit is too high .5 is more than enough for this problem

Cracker: 2015-01-20 03:19:52

this brings me to point 1... :P


Added by:jack(chakradarraju)
Date:2012-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64