You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

Acm 校赛开始了。刚进队的奶龙也想凑个热闹。作为啥算法也不会的糖龙，决定和大家玩个猜数游戏： 奶龙想了一个长度为 n 的 01 字符串 s。他会告诉你所有把 s 改变 k 位后的字符串，其中单次改变满足 s[i] = s[i] ^ 1。

你需要根据奶龙给出的这些改变后的字符串，推测奶龙心中想的原字符串。当你猜错时，奶龙会嘲笑你一次，并让你继续猜。

现在告诉你 n 和 k 的值，你为了减少被糖龙嘲笑的次数，最少才几次能保证猜对？

Input Format

第一行包含一个整数 t ，代表测试用例的数量。

每个测试用例包含一行两个整数，分别代表 n,k 。

Output Format

对于每个测试用例，输出一行一个整数，代表答案。

Sample

Hint

样例解释：假设奶龙心里想的是 010，那么他会告诉你 {110, 000, 011}。你根据这三个字符串一次就能猜对，所以输出1，并且你没有被糖龙嘲笑。 可以证明，只要n,k固定，不管奶龙心中所想是什么数列，答案唯一确定。

数据范围

• 20%：随机数
• 20%：Ai 给的
• 20%：奶龙梦到的
• 对于所有数据：1 <= k <= n <= 1e9
• 答案对 998244353 取模