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₁₀ * 4 = 1040₁₆, i.e. (1*10³+0*10²+4*10¹+0*10⁰)*4=(1*16³+0*16²+4*16¹+0*16⁰). 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₁<B₂ be positive integers, and a₀,a₁,…,a_k be integers in [0…B₁-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₁, B₂, 9<B₁<B₂<100, and two integer range elements, r₁, and r₂, 0<r₁<r₂<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₁<i<r₂, for which there is a positive integer c such that the digits of i in the base B₁, are exactly the same as the digits of i*c in the base B₂. 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