题目描述

Carol 有三个正整数 $x_1,x_2,x_3$。每次操作 Carol 可以选择指定两个数 $x_i,x_j$（$i \ne j$）和一个正整数 $k$，把 $x_i$ 修改为 $x_i \oplus k$，把 $x_j$ 修改为 $x_j \oplus k$。

Carol 想知道，她最少需要做多少次操作，可以使得这三个数满足 $x_1 + x_2 = x_3$。如果无论如何操作都无法做到，请输出 -1。

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 组询问：

每组询问一行三个整数 $x_1,x_2,x_3$。

输出格式

共 $T$ 行，每行一个整数，代表该组询问最少需要的操作次数。如果无解输出 -1。

3
5 6 11
3 2 1
5 5 7

0
1
-1

数据范围

对于 $30\%$ 的数据，$1 \le T \le 5$； 对于 $30\%$ 的数据，$1 \le x_1,x_2,x_3 < 32$； 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^5$，$1 \le x_1,x_2,x_3 \le 10^9$。