U140760 狭义公因子

$Seaway$是热爱读书的好孩子。 有一天，$Seaway$正在读书。他看到了这样的一段描写—— 闰土又对我说： “现在太冷，你夏天到我们这里来。我们日里到海边捡贝壳去，红的绿的都有，鬼见怕也有，观音手也有。晚上我和爹管西瓜去，你也去。” “管贼吗？” “不是。走路的人口渴了摘一个瓜吃，我们这里是不算偷的。要管的是獾猪，刺猬，狭。月亮底下，你听，啦啦的响了，狭在咬瓜了。你便捏了胡叉，轻轻地走去……” 我那时并不知道这所谓狭的是怎么一件东西——便是现在也没有知道——只是无端的觉得状如小狗而很凶猛。 “他不咬人么？” “有胡叉呢。走到了，看见狭了，你便刺。这畜生很伶俐，倒向你奔来，反从胯下窜了。他的皮毛是油一般的滑……” ——迅哥儿《故乡》

书里的描述让$Seaway$无限神往。他不禁想象：鲁迅大神写的“狭”到底是什么东西呢？但残酷的生活不允许他多做思考，他被数学老师拉去做数学题了。但是，在做题的时候，他还是控制不住地想着这个东西。数学书里的符号也好像变成了一个个古灵精怪的小“狭”，在他的眼前飞舞。 于是，他灵光乍现：原来恁地！“狭”是狭义的意思！怪不得这畜生很伶俐！ 他兴奋地抄起笔，在草纸上画出了自己的想象： 狭义公因子： 给定$x,y,a,b$，定义$a,b$在$[x,y]$内的最大公因子为狭义公因子，记作$\text{na-gcd}(a,b,x,y)$。

从文件$narrow.in$中读取数据。 第一行包括两个正整数$a,b$。第二行包括一个整数$T$，表示询问区间组数。接下来的$T$行，每行两个整数$x_i,y_i$。意义皆如题目描述所示。

输出到文件$narrow.out$中。 共$T$行，每行一个整数，表示$\text{na-gcd}(a,b,x_i,y_i)$。 若不存在合法的$\text{na-gcd}(a,b,x_i,y_i)$。输出`fake`。

【**数据范围**】 对于$40\%$的数据，$1\le a,b,x,y\le 10,1\le T\le 10$。 对于$80\%$的数据，$1\le a,b,x,y\le 1000,1\le T\le 100$。 对于全部数据，$1\le a,b,x,y\le 10^9,1\le T\le 10000$。