背景

背着包，拖着行李箱，在夕阳的余晖下，走在越来越繁华的郁金香路上，生命也好像变得无限漫长…… 而在这漫长的生命中，我只是一场在春天飘落的雨，潮湿了老巷子，滋润了......

描述

小鳄鱼有得到五个整数 $k$ ， $l_1$ ， $r_1$ ， $l_2$ 和 $r_2$ 。小鳄鱼希望你帮他收集郁金香路上的所有郁金香，一对有序数对 $(x, y)$是寻找郁金香的一个线索且满足以下条件 ：

• $l_1 \leq x \leq r_1$ .
• $l_2 \leq y \leq r_2$ .
• 存在一个非负整数 $n$ ，使得 $\frac{y}{x} = k^n$ .

格式

输入

第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例数。

每个测试用例的唯一一行包含五个整数 $k$ 、 $l_1$ 、 $r_1$ 、 $l_2$ 和 $r_2$ ( $2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9$ )。

输出

对于每个测试用例，在新行中输出郁金香线索的最大值。

样例

5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861

12
1999999987
6
1
197

注

在第三个测试案例中，匹配的有序对如下：

• $(5,15)$
• $(5,45)$
• $(6,18)$
• $(6,54)$
• $(7,21)$
• $(7,63)$

在第四个测试用例中，唯一有效的有序对是 $(1,1\,000\,000\,000)$

限制

1s, 1024KiB for each test case.