C. XOR Boss Fight
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a video game and trying to beat a boss with your friend! The boss has $$$x$$$ hitpoints. The two of you start off by dealing $$$y$$$ damage per turn. Due to how the game works, you two have special values that you can use to modify the damage you deal each turn. For a given special value $$$s$$$, the modification consists of setting $$$y$$$ to be equal to $$$y \oplus s$$$ where $$$\oplus$$$ denotes the bitwise XOR operation. Your friend has value $$$a$$$, while you have value $$$b$$$. Unfortunately, your friend does not care about optimality, and will perform his modification every turn (that is, set $$$y$$$ to be equal to $$$y \oplus a$$$). You however, want to beat the boss as fast as possible, and will therefore choose on every turn after your friend performs his modification whether or not to perform another modification of your own with your own value (that is, set $$$y$$$ to be equal to $$$y \oplus b$$$) before doing damage to the boss. Assuming you choose an optimal sequence of modifications, what is the minimum number of turns before you beat the boss?

More formally, given $$$x, y, a$$$, and $$$b$$$, you want to find the minimum number of terms in the sequence $$$c_1, c_2, \ldots, c_n$$$ such that $$$\sum_{i = 1}^{n} c_i \ge x$$$. Here, $$$c_0 = y$$$, and $$$c_i = c_{i - 1} \oplus a \oplus (b \cdot k)$$$, where $$$k \in \{0, 1\}$$$, and you choose the value of $$$k$$$ for each term.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.

The first and only line of each test case contains four integers $$$x$$$, $$$y$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq x$$$, $$$y$$$, $$$a$$$, $$$b \leq 10^9$$$).

Output

For each test case, output a single integer denoting the minimum number of turns required to beat the boss.

Example
Input
3
7 3 5 1
9 4 5 6
10 1 1 1
Output
1
2
10
Note

For the first testcase, if we choose to perform the modification on the first move, we deal $$$3 \oplus 5 \oplus 1 = 7$$$ damage, so we can defeat the boss in one move.

For the second testcase, if we choose to perform the modification on the first move, we deal $$$4 \oplus 5 \oplus 6 = 7$$$ damage, so the boss has $$$9 - 7 = 2$$$ health remaining after the first move. If we choose not to perform the modification on the second move, we deal $$$7 \oplus 5 = 2$$$ damage, so we can defeat the boss in two moves. It can be shown that this is a lower bound on the minimum number of moves needed to defeat the boss.