AT_ajo2024_final_d Shooting the Stars

数直線上に $ N $ 個の星があり、座標の小さい順に $ 1 $ から $ N $ までの番号が付けられています。星 $ i \ (1 \leq i \leq N) $ は座標 $ X_i $ にあり、明るさは $ A_i $ です。 AtCoder さんは、いくつかの星を写真に撮りたいと思っています。AtCoder さんは、数直線上の区間を好きなように選び、これに含まれる星を撮影します。ここで、写真に写る複数の星が、明るすぎて同一視されることがあります。これは以下の規則に従っています。 1. 星 $ i, j $ は、 $ \left|X_i - X_j\right| \leq A_i + A_j $ を満たすとき、同一視される 2. 星 $ i, k $ が同一視され、星 $ k, j $ が同一視されるとき、星 $ i, j $ は同一視される 3. 以上の規則で同一視されない星は、異なる星として写真に写る なお、撮影する区間に入らない星は、写真には写らず、**同一視の対象にもならない**ことに注意してください。 さて、撮影する区間をうまく選んだとき、最大でいくつの異なる星として写真に写すことができるでしょうか？ $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられます。ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味します。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられます。 > $ N $ $ X_1 $ $ A_1 $ $ X_2 $ $ A_2 $ $ \vdots $ $ X_N $ $ A_N $

答えを出力してください。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおける写真撮影の方法を $ 2 $ 通り示します。 1. 座標が $ 0 $ 以上 $ 5 $ 以下の区間を選ぶ場合: 星 $ 1, 2 $ が写真に写ります。 $ |X_1 - X_2| = 3, A_1 + A_2 = 2 $ なので、星 $ 1, 2 $ は別々の星として写真に写ります。 2. 座標が $ 0 $ 以上 $ 9 $ 以下の区間を選ぶ場合: 星 $ 1, 2, 3, 4 $ が写真に写ります。問題文中の 1 つ目の規則により、星 $ 1, 3 $ 、星 $ 2, 3 $ 、星 $ 3, 4 $ が同一視されることになります。それから問題文中の 2 つ目の規則により、星 $ 1, 2, 3, 4 $ はひとつの星として同一視されます。 このテストケースでは、最大で $ 2 $ つの異なる星として写真に写すことができ、そのひとつの方法として 1. の方法が挙げられます。2. の方法では $ 1 $ つの星として写真に写るので、最適ではありません。 $ 2 $ 番目のテストケースでは、最大で $ 3 $ つの異なる星として写真に写すことができ、そのひとつの方法として座標が $ 1 $ 以上 $ 9 $ 以下の区間を選ぶ方法が挙げられます。 $ 3 $ 番目のテストケースでは、星を含む区間をどのように選んでも、 $ 1 $ つの星として写真に写ってしまいます。 ### Constraints - $ T \geq 1 $ - $ 1 \leq N \leq 200\,000 $ - $ 0 \leq X_1 < \dots < X_N \leq 10^8 $ - $ 1 \leq A_i \leq 10^8 $ - $ T $ 個のテストケースにおける $ N $ の総和は $ 200\,000 $ 以下 - 入力はすべて整数