题目描述

整数 a 和 b 可能有多个公约数，我们可以使用欧几里得算法计算出最大公约数。

然而，李老师更关心某个整数区间内是否存在 a 和 b 的最大公约数。

例如 a=12,b=18，有公约数 1,2,3,6：

在整数区间 [2,3] 中有公约数 2,3，该区间内的最大公约数为 3。

在整数区间 [1,2] 中有公约数 1,2，该区间内的最大公约数为 2。

在整数区间 [4,5] 中则没有公约数。

请你找出指定区间 [s,t] 内 a 和 b 的最大公约数，若不存在，则输出 −1 。

对于 100% 的数据：

1≤a,b≤10^9, 1≤s≤t≤10^9