UVA10677 Base Equality

作为一名程序员，我时常因十进制与十六进制之间的繁琐转换而沮丧。既然 16 进制如此实用，为何日常计数却采用 10 进制？显然因为并非所有人都是计算机爱好者。也许有一天世界会认识到十六进制的优势，但在此之前，我必须掌握进制转换——毕竟同一数字在不同进制下的表象往往大相径庭。 不过数字在不同进制间可能呈现奇特关联。例如： $1040_{10} \times 4 = 1040_{16}$ 即满足： $$ (1 \times 10^3 + 0 \times 10^2 + 4 \times 10^1 + 0 \times 10^0) \times 4 = (1 \times 16^3 + 0 \times 16^2 + 4 \times 16^1 + 0 \times 16^0) $$ 这引出一个问题：**何时某数在基数 $B_1$ 下的数字序列，恰好等于其倍数在基数 $B_2$ 下的序列？** **形式化定义：** 给定 $B_1 < B_2$（正整数），数字序列 $a_0, a_1, \ldots, a_k$（$\forall a_i \in [0, B_1 - 1]$）。 是否存在正整数 $c$ 满足： $$ \left( \sum_{i=0}^k a_i \times B_1^i \right) \times c = \sum_{i=0}^k a_i \times B_2^i $$

第一行输入测试用例数 $n$（正整数）。 接下来 $n$ 行每行包含四个整数： $B_1, B_2, r_1, r_2$ 满足约束： $9 < B_1 < B_2 < 100$ $0 < r_1 < r_2 < 10000$ **注意**：所有输入均为十进制数。

对每个测试用例，在区间 $(r_1, r_2)$ 内寻找最大整数 $i$ 满足： 存在正整数 $c$，使得 $i$ 在 $B_1$ 进制下的数字序列与 $i \times c$ 在 $B_2$ 进制下的数字序列**完全相同**（数字顺序和数值完全一致）。 若存在满足条件的 $i$，输出该整数； 若不存在，输出字符串`Non-existent.`

### 样例解释 1. **1040**： $1040_{10} = (1,0,4,0)_{10}$ $1040_{16} = (1,0,4,0)_{16} = 4160_{10}$ 满足 $1040 \times 4 = 4160$ 2. **4240**： $4240_{10} \times 4 = 16960 = 4240_{16}$ 3. **9240**： 在 $B_1=11, B_2=14$ 时存在对应 $c$ 满足条件 ### 数据范围 - 进制范围：$10 \leq B_1 < B_2 \leq 99$ - 数值范围：$1 \leq r_1 < r_2 \leq 9999$