牛牛变魔术
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

牛牛是个魔术师,它拥有两个无限容量的瓶子  和  。有一天表演魔术,某位观众要求牛牛变出一瓶刚好装有  毫升的饮料。

此时,瓶子  装有  毫升的饮料,瓶子  装有  毫升的饮料,牛牛每次操作可以把其中一个瓶子的任意整数(可以是0)毫升的饮料倒入另一个瓶子,并且每次操作结束后,两个瓶子的饮料毫升都会增加一倍

例如:瓶子  有  毫升,瓶子  有  毫升,一次操作把瓶子  的  毫升倒入瓶子  ,此时瓶子  有  毫升,瓶子  有  毫升,操作结束的瞬间,瓶子  变为  毫升,瓶子  变为  毫升,此时一次完整的操作结束。

由于观众耐心有限,牛牛需要用最少的操作次数来变出一瓶刚好  毫升的饮料,你能告诉它吗?如果一开始瓶子  或者  已经有  毫升,那么操作次数是  。如果不管怎么操作,都无法达到  ,输出 

输入描述:

第一行包括一个整数  ,表示询问的组数。

接下来  行,每行包括三个整数   

输出描述:

对于每组询问输出一行,表示最小操作次数。
示例1

输入

复制
2
1 3 1
4 4 2

输出

复制
0
1

说明

   已经有一个瓶子达到  的要求,不用操作,输出  。

   瓶子  倒入  毫升给瓶子  ,变成   ,在结束的瞬间变成   次操作即可。