B. How Aswad Use Telegram?
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$\textit{Aswad}$$$ is a member of a Telegram group chat with $$$n$$$ participants, he has a unique communication style. Although $$$\textit{Aswad}$$$ he doesn't like engaging in conversations, he still like to participate in the group by responding to messages.

However, instead of responding immediately, $$$\textit{Aswad}$$$ waits for a set amount of time before sending a message. Specifically, $$$\textit{Aswad}$$$ waits for $$$k$$$ minutes after the previous message is sent before responding.

It's $$$\textbf{important}$$$ to note that if another message is sent during the waiting period, $$$\textit{Aswad}$$$ will ignore the previous message and will wait for a new $$$k$$$ minutes. This approach allows $$$\textit{Aswad}$$$ to take his time in crafting a response and to avoid getting caught up in the rapid pace of the chat.

Given a list of $$$m$$$ timestamps for when messages were sent in the group chat, and the number of minutes $$$k$$$. your task is to determine how many messages $$$\textit{Aswad}$$$ has sent in the group chat.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n,k$$$, and $$$m$$$, where $$$n$$$ represents the number of members in the group chat, $$$k$$$ represents the time in minutes that $$$\textit{Aswad}$$$ waits before responding, and $$$m$$$ represents the number of messages sent in the group chat $$$(1 \leq n \leq 1000 , 1 \leq k , m \leq 1440)$$$.

The next $$$m$$$ lines each contain an $$$ID$$$ for the participant who sent the message, and a timestamp in the format HH:MM, representing the time when the message was sent in the group chat $$$(1 \leq ID \leq n , 0 \leq HH \leq 23 , 0 \leq MM \leq 59)$$$.

Output

For each test case, output a single integer on a new line representing the number of messages that $$$\textit{Aswad}$$$ has sent in the group chat.

Examples
Input
3
1 1 1
1 00:00
1 10 1
1 23:59
6 5 5
1 01:00
2 02:00
1 03:00
3 03:06
3 03:07
Output
1
1
4
Input
1
4 15 6
1 03:45
3 04:00
4 04:07
1 04:30
3 04:41
2 06:09
Output
3
Note

in the second example: $$$\textit{Aswad}$$$ will respond to the third, fifth and the sixth message because the message after each of them was sent exactly after k minuites, so the answers will be 3.