题目描述

《蜘蛛侠：多元宇宙》上线了，小红的朋友设计了一个蜘蛛侠小游戏请小红试玩。

这是一个二维平面小游戏，玩家操控蜘蛛侠利用蛛丝或者爬墙来移动。假如现在蜘蛛侠在$(x,y)$,它可以移动的方式有：

1.利用蛛丝实现远距离移动到 $(x+k,y+k)$ 或 $(x+k,y-k)$ , $k$是任意整数。

2.跳跃到 $(x+a,y+b)$ , 其中$|a|+|b|=3(1≤|a|,|b|≤2)$ 。

图示如下：

蜘蛛侠在图中位置时，上方格子中为1的是蜘蛛侠能用第一种方式一步到达的地点，为2的是能用第二种方式一步到达的的地点。 假如小红现在操控蜘蛛侠坐标为 $(x_1,y_1)$ ,他跳到 $(x_2,y_2)$ 最少需要多少次操作?

输入描述

输入第一行一个整数 $t(1≤t≤100)$ 表示询问组数。

接下来t行, 每行四个整数 $x_1,y_1,x_2,y_2(-10⁹≤x₁,y₁,x₂,y₂≤10⁹)$。

输出描述

一个整数， 代表最小的操作次数。

样例1

样例输入

4
1 1 1 1
1 1 5 5
1 1 4 1
1 1 -1 -3

样例输出

0
1
2
2