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
dqyz_hwk: 2020-12-16 02:27:38

I solve it with hash with lcm

Shubham Jadhav: 2020-06-26 21:09:53

KMP not necessary to solve this problem

kira28: 2016-12-26 14:24:14

How can one solve this problem in 5 lines of code??

ashishranjan28: 2016-09-22 14:26:08

gcdString :)

Mayank Garg: 2015-12-31 15:14:37

if u get it .. it wont take more than 5 lines :P

sonupmandal: 2015-12-21 05:03:34

Did without kmp..
Simple logic....:-)

dwij28: 2015-10-05 01:14:33

Good one.. I did it in python but my algorithm is not very efficient and gives a TLE in c++ while using std::string and SIGSEGV while using C-style strings. Feels bad.. I will try this question again with a fresh mind maybe .

Archangel: 2014-12-22 07:29:58

i read the problem wrong first costed me 2 WA's, kmp is enough to solve this problem

Yash Jain: 2014-12-15 14:11:27

@praveen123 pls check my code 13171761 . it is showing right output in ideone but SIGSEGV error here.

psyclaudeZ: 2014-08-26 04:34:35

Nice problem. Learned a new way to use KMP! (but I'm wondering how can I solve the problem in 5 lines? )


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: