# Problem H

Base equality

## Source code: base.*

Numerous are the moments I as a
programmer have been frustrated by the tedious conversions between decimal
numbers and hexadecimal ones. Why have we chosen 10 as a base in our everyday
numerical presentations, when 16 seems so practically appealing? Obviously
because everyone is not the computer geek I am. Maybe some day the world will
fully realise the benefits of the hexadecimal system. In the meantime I have to
learn to master the base conversions since most of the time numbers do not
resemble one another in different bases.

Sometimes peculiar relationships
emerge among the different base representations of numbers though. For
instance, I noticed just the other day that 1040_{10 }* 4 = 1040_{16},
i.e. (1*10^{3}+0*10^{2}+4*10^{1}+0*10^{0})*4=(1*16^{3}+0*16^{2}+4*16^{1}+0*16^{0}).
It made me wonder how often this is the case, that is, the digits of a number
in one base, are exactly the same as the digits of a multiple of the number in
another base. Formally, let *B*_{1}<*B*_{2} be positive integers, and *a*_{0},a_{1},
,a_{k}
be integers in [0
*B*_{1}-1].
For which *a*_{i}s is there a
positive integer *c* such that

_{}

### Input

On the first line of input is a
positive integer *n* telling the number
of test cases that follow. Each test case is on a line of its own and consists
of two integer bases *B*_{1}, *B*_{2}, 9*<B*_{1}<B_{2}<100*, *and two integer range elements, *r*_{1}, and *r*_{2},
0*<r*_{1}<r_{2}<10000*.* Notice that all numbers in the input
are given in the base 10.

### Output

For each test case, there should
be one row containing the largest integer *i*,
fulfilling *r*_{1}<i<r_{2},
for which there is a positive integer *c*
such that the digits of *i *in the base
*B*_{1}, are exactly the same
as the digits of *i*c* in the base *B*_{2}. If no such integer *i *exists, output the text
Non-existent..

Example input:
Example output:

4
1040

10 16 1 2000
4240

10 16 1 4999
Non-existent.

10 14 10 9999
9240

11 14 10 9999