T国的首都十分繁华，进入当地幼儿园学习的标准也是相当苛刻。这所幼儿园很奇怪，想进入幼儿园的孩子都必须通过一个名为“分数游戏”的入学选拔才可以进入学习。
游戏规则如下：

1. 考官随机给你两个分数 a / b 和 c / d（分子分母均为整数）。
2. 每一回合你可以选择 a, b, c, d 中的一个数，使其乘以一个任意整数，然后由考官判定现在的两数是否相等。

现在你需要帮助 小t 找到满足考官要求的最小回合数。

第一行包含一个整数 t ( 1 ≤ t ≤ 1e4 )——测试用例的数量。然后遵循每个测试用例的描述。
每个测试用例的唯一一行包含四个整数 a、b、c 和 d ( 0 ≤ a, c ≤ 1e9,1 ≤ b, d ≤ 1e9 )——最初给考官给 小t 的两个分数的分子和分母。

对于每个测试用例，打印一个整数——满足考官要求的最小回合数 。