수직선 위에 $n$마리의 캥거루가 있으며, $i$번째 캥거루는 처음에 양의 좌표 $c_i$ (즉, $c_i > 0$)에 있고 두 개의 보폭 $a_i$와 $b_i$를 가지고 있습니다.

캥거루들은 키보드의 버튼 1, 2, 3, 4를 눌러 제어합니다. 눌린 버튼에 따라 모든 캥거루가 동시에 이동합니다. 구체적으로, $x_i$를 $i$번째 캥거루의 현재 좌표라고 할 때:

• 버튼 1: $(x_i + a_i)$로 이동합니다.
• 버튼 2: $(x_i - a_i)$로 이동합니다.
• 버튼 3: $(x_i + b_i)$로 이동합니다.
• 버튼 4: $(x_i - b_i)$로 이동합니다.

두 마리 이상의 캥거루가 같은 좌표에 있는 것이 허용됩니다. 이동 중에 두 캥거루가 만나면 그냥 서로를 통과해 지나갑니다.

버튼은 원하는 만큼 얼마든지 누를 수 있습니다. 작업 후 음수 좌표에 있는 캥거루의 수(즉, $x_i < 0$인 캥거루의 수)를 최대화하세요.

입력

여러 개의 테스트 케이스가 있습니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다. 각 테스트 케이스에 대하여:

첫 번째 줄에는 캥거루의 수를 나타내는 정수 $n$ ($1 \le n \le 2 \times 10^5$)이 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 $i$번째 캥거루를 설명하는 세 정수 $a_i$, $b_i$, $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$)가 주어집니다.

모든 테스트 케이스에서 $n$의 합은 $2 \times 10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 작업 후 음수 좌표에 있는 캥거루의 최대 수를 나타내는 정수 하나를 한 줄에 출력합니다.

예제

입력 1

2
4
1 1 1
-1 3 4
0 -2 7
-5 0 10
1
0 0 1

출력 1

3
0