D. D.跃迁

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

某天yzy爆破了hlbt

yzy:你看什么呢!

hlbt:就..就...没啥

yzy:你这么闲,要不你就别在这弄了,回班上课吧

(hlbt回头)

yzy:这样,我给你出道题,你做出来就在这好好搞竞赛,做不出来你就回班上课。

hlbt:行。

显然hlbt划了很久的水,他已经不知道如何写mian函数了,于是他找到了你。热心的你显然是乐于助人的,不然你就会失去这很水的100分,所以你拿到了题。

儒略日1145141919810日,yzy住在维度是1的世界里,无趣的生活使他萌生了搬家到不同维度世界的念头。这样就必须用到世界跃迁技术,由于当时xyxer还没有完善世界跃迁技术,众多的局限性导致世界跃迁技术仅允许人们跃迁到以当前世界维度为倍数的维度所对应的世界。人类的思维只能理解维度不超过 n 的世界,超出之后就无法保持理智。事实上每个维度都只对应一个世界,维度分别为1到正无穷之间的正整数。yzy想搬到他看起来较为安全的世界。yzy认为一个维度的世界较为安全当且仅当这个维度仅能从两个世界跃迁到(包含这个世界本身),但符合这样条件的世界还是很多,再加上如果太安全就会再次感到生活的乏味,所以他决定冒点险

他希望搬到尽可能最大的维度为 连续的 k 个较为安全的世界维度和 的世界。对于连续的较为安全的世界,yzy将其定义为相邻两个较为安全的世界的维度之间不存在任何一个维度所对应的世界为较为安全的世界。yzy简单地思考了一下,发现有时好像并不能搬到一个满足条件的世界。如果没有满足条件的世界,他只好放弃搬家;如果有,他就会努力地制定一个跃迁的计划并付诸行动。那么他到底能不能搬到一个满足条件的世界安家呢?如果能,请你告诉他这个世界的维度;如果不能,请委婉地说出"Sorry,that's impossible."。

你看完题面,觉得这题太简单了,马上就开始写。

输入格式

本题采用多组数据测试。

第一行一个整数T代表测试数据组数。

对于每组测试数据,一行两个整数n,k。

输出格式

对于每组测试数据,若有满足条件的世界,则输出一个整数ans;若没有,则输出"Sorry,that's impossible."(不包含引号)

样例

input

3
20 2
20 3
20 4

output

18
15
17

yzy认为这题太简单了,而聪明的你一定是不需要样例解释的

数据范围与提示

对于20%的数据, 1<=n<=500 1<=T<=200

对于40%的数据, 1<=n<=1000000 1<=T<=1000

对于另外20%数据, k<=2

对于100%的数据,保证 1<=n,k<=10000000 1<=T<=100000