题目描述

作为一个程序员，我经常为十进制数和十六进制数之间繁琐的转换感到沮丧。为什么我们要选择$10$作为日常数字表示的基础，而$16$看起来如此实用？显然是因为并非所有人都是像我这样的计算机极客。也许有一天世界会完全认识到十六进制系统的优势。在此期间，我必须学会掌握进制转换，因为大多数时候数字在不同进制下看起来并不相同。

不过，有时不同进制表示的数字之间会出现奇特的关系。例如，我最近注意到$1040_{10} \times 4 = 1040_{16}$，即$(1\times10^3+0\times10^2+4\times10^1+0\times10^0)\times4=(1\times16^3+0\times16^2+4\times16^1+0\times16^0)$。这让我好奇这种情况发生的频率有多高，即一个数字在某个进制下的数字序列，恰好是该数字的某个倍数在另一个进制下的数字序列。

输入格式

第一行输入一个正整数$n$，表示测试用例的数量。每个测试用例单独一行，包含两个整数基数$B_1$、$B_2$（$9 \leq B_1 < B_2 \leq 100$）和两个整数范围元素$r_1$、$r_2$（$0 < r_1 < r_2 \leq 10000$）。注意输入中的所有数字都是以$10$为基数给出的。

输出格式

对于每个测试用例，输出一行包含满足以下条件的最大整数$i$（$r_1 < i < r_2$）：存在正整数$c$，使得$i$在基数$B_1$下的数字序列与$i \times c$在基数$B_2$下的数字序列完全相同。如果不存在这样的整数$i$，则输出"Non-existent."。

输入样例 1

4
10 16 1 2000
10 16 1 4999
10 14 10 9999
11 14 10 9999

输出样例 1

1040
4240
Non-existent.
9240

题目来源

2001年瑞典/挪威编程锦标赛