C. 正难则反

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

题目描述

「正难则反」是一个重要的问题求解思想。它的含义正如字面:当问题从正面、正向的角度很难解决时,不妨从反面、反向的角度来考虑问题。

具体地,请你解决如下问题:

对于一个正整数二元组 ,我们可以将其变为 或 ,并把这种变化称为一次操作。

给定两个正整数二元组 ,问 能否通过若干次操作变为 ?若能,给出操作的最少次数;若不能,输出 -1。

形式化地,

给定一个正整数二元组 ,对于任意 ,我们设 ,则 可以是且仅可以是 或 。

然后给出另一正整数二元组 ,问是否存在一个二元组序列 ,如果存在,给出 的最小值,如果不存在,输出 -1。

输入格式

第一行一个正整数 。

接下来 行,四个正整数 ,含义如题。

输出格式

行,每行一个数,表示你的答案。

样例

样例输入

2
3 7 3 10
3 4 2 9

样例输出

1
-1

数据范围与提示

对于前 的数据,保证 ,答案 。

对于所有数据,,输入给出的所有数字都在 long long 范围内。

友情提示:部分分可以直接搜索。数据规模有梯度,越快的做法可以得越多的分。