1268:罗少粉丝群

时间限制: 2 S | 内存限制: 65536 KB
Accept: 12 | Submit: 44
[提交] [状态] [讨论版]
描述

出于对罗少的仰慕,你加入了罗少粉丝群。当你想在群里@罗少的时候发现,大家的群名片全部都是罗少,为了区分他们,我们给他们分别编一个号,简称罗少1、罗少2、罗少3...


于是你无从下手,但经过几天的聊天你得到了以下信息:

1、群里除了你总共有 n 个人,其中一个是真罗少。

2、这 n 个人中有 a 个人是罗少的黑粉,因为他们总说假话(比如罗少好帅之类的)。

现在你可以与群里任何人私聊任意次来找到真正的罗少,但是你只可以问两种问题:

1、真罗少是罗少几?

2、你是真罗少吗?

值得注意的是,罗少的黑粉只说假话,其他人只说真话。

你不想浪费太多时间,于是决定用最少的次数问出来谁是罗少,但是黑粉会尽可能通过他们的操作来浪费你的时间。

输入

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 10000)

每组案例有两个正整数n、a。(1 <= n <= 1e9,0 <= a < n)

输出

你最少问多少次可以找到真正的罗少,如果你找不到输出-1。

每组案例输出结束以后都要换行。

样例输入

2

2 0

2 1

样例输出

1

-1

HINT

在第一组案例中,群里只有两个人,而且没有黑粉,此时无论你问谁<真罗少是罗少几>他们都会指认真罗少的编号。

在第二组案例中,群里只有真罗少和一个黑粉,无论你如何询问这两个人,他们的回答都无法让你确定谁是真罗少。

来源
TKK-ICPC Round#3