BHAT007 - Nikhil Problem

Nikhil is a very interesting and creative character. Nikhil had best friend whose name was Kasat. Kasat was inspired from SKG, a mathematics professor having  an experience of 30 years of teaching in IIT Kanpur, So he decided to open Mathematics classes named as “SAI KRIPA GANIT BHANDAR”. But unfortunately no one joined his classes as the fees he charged was too low compared to other institutions, so people thought that he is not a good teacher and his wait for the students continued, but the best friend Nikhil was not able to see his friend Kasat in such a gloomy situation. So to boost Kasat’s spirit he became the only student of  the “SAI KRIPA GANIT BHANDAR”.

Nikhil  learned addition multiplication in different number system (like binary number system: base 2, octal number system: base 8, Hexagonal number system, Kasat number system : base 7, Shrotriya number system: base 3, bhat number system: base 13, rajnikant number system base: 100, ravikant number system base:101 etc. ).

Nikhil was given daily assignment on this but helping friends and being lazy are two different things, all he could help Kasat was to join coaching classes and completing those complex assignment were not  his cup of tea. Kasat thought an innovative idea for Nikhil to sharp his mind in the field of number system. So, he gives the same type of problem daily in assignment.

Problem:

x(b1) + y(b1) = z1

x(b2) + y(b2) = z2

x(b): number x in base b number system .

x and y are two numbers (must be valid in decimal (i.e. base 10), base b1 and base b2 number system like 1A is not valid in base 10 i.e. decimal number system but valid in base 16, 17, 18, etc.)

z1 and z2 are the results of addition of x and y number in base b1 and b2 number system respectively . 

If z1 and z2 are similar then answer is "yes" else "no".

0 <= x <= 2100

0 <= y <= 2100

1 < b1 <= 100

1 < b2 <= 100

Your task is to write the program to solve the problem of Nikhil.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing four integers x, y  (0 <= x, y <= 2100) and b1, b2 (1 < b1, b2 <= 100).

Output

Your program should print one line of output for each test case. Output can either be "yes" or "no" .

Example

Input:
3
10 01 2 10
11 11 2 10
12 12 8 10
Output:
yes
no
yes

Added by:om
Date:2011-07-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:inspired from interesting character of nikhil :)

hide comments
2011-08-05 05:31:53 Seshadri R
The letters a, b, c, d, e and f (input will be in lower or upper case?) can be assumed till hexadecimal base. What are the single letter characters beyond this? For example, which letter would be used to represent 99 to the base 100?
2011-07-27 23:47:31 Praveen Vaka
the second test case (12 12 2 10) in sample input doesn't conform to the input restriction that x and y must be valid in base b1 and b2 :)
2011-07-27 23:47:31 Harshil Tamrakar
for all those who don't know ravikant-
he is the ultimate version of rajnikant
2011-07-27 23:47:31 Harshil Tamrakar
our college story awesome
ravikant no system should have been undefined.
2011-07-27 23:47:31 Problem Solver
Nice story and problem :)
2011-07-27 23:47:31 blashyrkh
I got AC. So I can answer:
i) yes
ii) 31 bytes is enough (+1 for '\0' in C/C++)
iii) yes
iv) addition
2011-07-27 23:47:31 [Rampage] Blue.Mary
Several questions, or some suggestions about a clear problem description:
(i)The input x and y, in my opinion, are two strings, made of digits '0' - '9'. Leading zeros are OK.
(ii)The length of x and y: 100, or some other value, like - when x (or y) in base b1 (or b2) has been transformed to a base 10 number, its value will be less than 100?
(iii)What does "Similar" mean? Two absolutely same digit strings (both without leading zeroes)?
(iv)The operator. Which one is the one I should use in calculation? '+' or '*'? Two different explanations in problem description.
2011-07-27 23:47:31 neerajcrespo
beautiful problem statements.. :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.