题目描述

FitnessGram Pacer Test 是一项多阶段有氧能力测试，随着测试进行会变得越来越困难。20 米 Pacer 测试将在 30 秒后开始。请在起点排队。每当你听到这个声音时应该完成一圈。Ding！记得直线奔跑，并尽量坚持跑下去。听到“start”时测试开始。各就各位。准备！……

Farmer John 正在参加 FitnessGram Pacer Test！Farmer John 每分钟可以跑到体育馆对面。因此，在每分钟开始时，FJ 可以选择跑到体育馆的另一侧，或者停留在原地。如果他选择跑到另一侧，他可以获得 1 分。

FJ 将一直跑步，直到第 $m$ 分钟开始时为止。最初（第 $0$ 分钟开始时），FJ 处于体育馆的起始一侧，我们将其记为第 $0$ 边。体育馆的另一侧记为第 $1$ 边。

Pacer Test 的音频会播放 $n$ 次。在第 $a_i$ 分钟开始时，FJ 必须位于体育馆的第 $b_i$ 边。

在满足音频要求的前提下，FJ 至多可以获得多少分？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \times 10^5, \ n \leq m \leq 10^9$），分别表示音频要求的数量和总分钟数。

接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i \leq m, \ b_i \in \{0,1\}$），表示音频的第 $i$ 条要求。在第 $a_i$ 分钟开始时，FJ 必须位于第 $b_i$ 边。

保证对于所有 $i > 1$，均有 $a_i > a_{i-1}$。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出 FJ 能获得的最大分数。

说明/提示

对于第一个样例测试：

• 第 $0$ 分钟，FJ 可以停留在第 $0$ 边。
• 第 $1$ 分钟，FJ 可以跑到第 $1$ 边，获得 $1$ 分。
• 紧接着在第 $2$ 分钟开始前，音频要求 FJ 处在第 $1$ 边。此时 FJ 的确在第 $1$ 边。
• 第 $2$ 分钟，FJ 可以跑到第 $0$ 边，再获得 $1$ 分。
• 第 $3$ 分钟，FJ 可以停留在第 $0$ 边。
• 紧接着在第 $4$ 分钟开始前，音频要求 FJ 处在第 $0$ 边。此时 FJ 的确在第 $0$ 边。
• 由于已经到达第 $4$ 分钟的开始，测试就结束了。FJ 总共获得 $2$ 分。

相关示意图：

由 ChatGPT 5 翻译

样例

3
2 4
2 1
4 0
2 7
1 1
4 0
4 9
1 0
2 0
6 1
9 0

2
7
6