题目描述

给定两个数 $x,y$。你可以进行下面两种操作任意多次：

• 花费 $c$ 的代价，令 $x\leftarrow x \operatorname{AND} a$。

• 花费 $d$ 的代价，令 $x\leftarrow x \operatorname{OR} b$。

其中 $\operatorname{AND}$ 和 $\operatorname{OR}$ 分别表示按位与运算和按位或运算。

你需要求出将 $x$ 变为 $y$ 的最小代价，如果做不到，输出 $-1$。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

对于每组数据，仅一行，包含六个整数 $x,y,a,b,c,d$。含义见题面。

输出格式

一行一个整数，表示答案。

5
1 15 2 14 3 5
1 3 3 14 9592 382
0 5 2 5 3492 12
194928 90283 59980 344444 182 959304
767894141 142877299 413934195 252884611 340885 421240

5
9974
12
-1
762125

提示

样例解释

• 对于第一组数据，可以花费 $5$ 的代价或上 $14$，得到 $15$，满足要求。可以证明，没有更优的方案。

• 对于第二组数据，可以先花费 $382$ 的代价或上 $14$，得到 $15$，再花费 $9592$ 的代价与上 $3$，得到 $3$，满足要求。总代价为 $9974$。

• 对于第四组数据，可以证明不存在方案满足要求。

数据规模与约定

本题采用捆绑测试。

• Subtask 0（0 pts）：样例。
• Subtask 1（10 pts）：$x,y,a,b< 2^3$。
• Subtask 2（10 pts）：$y=2^k-1$，$k$ 是一个非负整数。
• Subtask 3（30 pts）：$x,y,a,b< 2^{10}$。
• Subtask 4（20 pts）：$c=d=1$。
• Subtask 5（30 pts）：$x,y,a,b< 2^{30}$。

对于所有数据，保证 $1\le T\le 10^5,0\le x,y,a,b,c,d< 2^{30}$。