BAPM - Base and Power

no tags 

Little boy Arik learned exponent formulas from his math teacher. Teacher taught him, If you have such expression x^a=y^b then,

  1. If x=y then a=b.
  2. If a=b then x=y.

Arik learned this awesome thing. After a while, he was playing with different numbers. He got confused a little bit. Sometimes x not equal to y and a not equal to b but x^a=y^b. Such as 2^4=4^2. Your task is to help Arik to determine if x^a is equal to y^b or not.

Input

Input starts with an integer T (<= 30) denoting the number of test cases.

For each case, you will given 4 integers x, a, y, b.

x and y are two bases where 0 < x, y <=100000000000001.

Two exponents are given as a and b where 0 <= a, b <= 100000000000001.

Output

Print "Yes" without quote in a single line if x^a=y^b, "No" otherwise.

Example

Input

2
2 4 2 4
3 4 4 3

Output

Yes
No

hide comments
jazib_official: 2018-01-10 11:14:59

Easy af, AC in one go

vishalsingh17: 2018-01-02 05:36:56

Last edit: 2018-01-02 06:04:14
barishnamazov: 2018-01-01 14:24:07

Add more tests.. My code got AC but outputs "Yes" for this case:
1
1 1 1000000008 1


Added by:Sarwar
Date:2017-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All