問題文

4097 年の CatCoder では、CatCoder Knapsack Contest（以下、CKC と略します）を開催することになりました。

各問題案にはそれぞれ難しさと面白さの 2 つのパラメータが 1,2 の 2 段階で割り振られており、難しさが i\ (i = 1,2) で面白さが j\ (j = 1,2) である問題案は A_{i,j} 個あります。

CKC を 1 回開催するためには、難しさの和と面白さの和がそれぞれちょうど X,Y であるような問題案の集合を使用する必要があります。 各問題案は高々 1 回の CKC にしか使用出来ません。

CKC を最大で何回開催出来るかを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 10^5
• 1 \le X,Y \le 10^9
• 0 \le A_{i,j} \le 10^9
• 入力される値は全て整数

入力例 1

3
5 6
3 3 3 3
1 1
0 1 2 3
3 3
1000000000 1000000000 1000000000 1000000000

出力例 1

2
0
2000000000

1 つ目のテストケースについて、以下のように問題案を使用することにより、CKC を 2 回開催出来ます。