問題文

$1$ から $N$ までの番号がつけられた $N$ 人の人がある地点間を往復するレースを行いました。このレースについて、以下の情報が残されています。

• 往路のタイムの早い順に順位をつけると、どの $2$ 人のタイムも異なっており、人 $i\\ (1 \\leq i \\leq N)$ は $i$ 位であった。
• 往復のタイム（往路のタイムと復路のタイムの合計）の早い順に順位をつけると、どの $2$ 人のタイムも異なっており、人 $i\\ (1 \\leq i \\leq N)$ は $P_i$ 位であった。
• 復路のタイムが最も早かった人（複数人いる場合はその全員）に復路の区間賞が与えられた。

ここで、$P_1, P_2, \\dots, P_N$ は $1, 2, \\dots, N$ の並べ替えです。

このとき、復路の区間賞を与えられた可能性のある人は何人いるでしょうか？

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

制約

• $1 \\leq T \\leq 500$
• $2 \\leq N \\leq 10^3$
• $P_1, P_2, \\dots, P_N$ は $1, 2, \\dots, N$ の並べ替えである
• 入力される数値は全て整数
• $1$ つの入力に含まれるテストケースについて、$N$ の総和は $10^3$ 以下

入力

入力は以下の形式で標準入力から与えられる。

$T$ $\\mathrm{case}_1$ $\\vdots$ $\\mathrm{case}_T$

各テストケース $\\mathrm{case}_i\\ (1 \\leq i \\leq T)$ は以下の形式で与えられる。

$N$ $P_1$ $P_2$ $\\cdots$ $P_N$

出力

$T$ 行出力せよ。$i$ 行目 $(1 \\leq i \\leq T)$ には、 $i$ 番目のテストケースの答えを出力せよ。

入力例 1

3
2
2 1
4
1 2 3 4
20
13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17

出力例 1

1
4
7

• $1$ つ目のテストケースでは、$2$ 人でレースを行い、復路において人 $2$ が人 $1$ を抜かしています。この場合、復路の区間賞は人 $2$ に与えられます。
• $2$ つ目のテストケースでは、復路で順位が変動しておらず、どの人も復路の区間賞が与えられた可能性があります。