IITKWPCJ - Check the string Powers

no tags 

Feluda likes strings and mathematics very much. As Feluda is still a child, he was only recently introduced to concept of powers. Being a novice guy, he thinks about powering strings as well as numbers. He defines A^n (A powered to n) to be A + A + ... + A which is a concatenation of n copies of A. For example "bhupkas"^2 = "bhupkasbhupkas".

He wants to check if given two strings A and B, can he find such positive integers n and m so that A ^ n = B ^ m. We are only interested in YES/NO answer, no need to give n and m values.

Input

First line contains integer T: number of test cases (T <= 100).

Single line per test case containing strings A and B. Both will be non-empty, of lengths of at most 10^5, composed only of lower case letters.

Output

For each test case, output "YES" if it possible to find integers n and m so that A ^ n = B ^ m or "NO" otherwise (quotes for clarity).

Example

Input:
3
a a
ab ba
praveen praveen

Output:
YES
NO
YES

hide comments
vishal chaudhary: 2013-09-02 23:10:53

@praveen123 giving WA ...my code is working fine ...plz check ...submission id : 9970515

Bumbler: 2013-08-23 18:32:15

code in python 3.3 NZEC & same in python 2.7 worked..

Amitayush Thakur: 2013-08-22 18:07:03

very weak test case got AC for
aabba aabbaaa
YES
answer should be NO

fitcat: 2013-08-22 15:49:13

Test cases are weak. Here is another example:
aab aabbaa should be NO but answering YES can get AC.

Miguel Oliveira: 2013-08-22 15:49:13

cool problem, but the runtimes are weird. i'll wait for the rejudge when you add cases

dawdler: 2013-08-22 15:49:13

@KARANN I get no for raaga raagaraagaraa using my program but the judge says wrong answer
any tricky test case...?

praveen123: 2013-08-22 15:49:13

I will update test case upto This Sunday, then I would rejudge all the solutions

GAURANGA: 2013-08-22 15:49:13

test cases are weak.
wil get even work on test case:
raaga raagaraagaraa..YES
ANSWER Should b no..:P

[Lakshman]: 2013-08-22 15:49:13

Haha Fastest python solution Got AC with python in 0.0.


Added by:praveen123
Date:2013-08-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource: