Route Table Lookup Change Counter

In IP routing, routers select a route table entry whose destination and mask match the destination IP address of a packet. The matching is done by converting both the packet’s destination IP and the route entry’s destination IP into 32-bit binary strings. Given a mask length x, only the first x bits are compared. If multiple entries match, the one with the longest mask (i.e. the most specific match) is selected. Note that even if the next-hop addresses are different for two matching routes, they are considered the same if the destination address and mask length are identical.

Over a period of time, the router’s forwarding decisions (i.e. the choice of the best matching route) may change as the routing table is updated. Your task is to determine the number of times the chosen route entry changes over a sequence of routing table snapshots. A change is defined as the best matching route (identified by its destination IP and mask length) being different from that chosen in the previous snapshot. If no route matches, the result is considered null for that snapshot.

The IP addresses are given in the standard dotted-decimal notation. For converting an IP address to a binary string, split the address into 4 integers (each between 0 and 255), convert each into an 8-bit binary string, and concatenate them. For example, 192.168.1.253 becomes 11000000 10101000 00000001 11111101.

Input Format:

• The first line contains the target IP address whose routing decision changes are to be monitored.
• The second line contains an integer T, representing the number of routing table snapshots.
• For each snapshot:
• The first line contains an integer N, the number of route entries in that snapshot.
• Each of the next N lines contains three tokens: the destination IP address, the mask length (prefixed with '/' e.g. /24), and the next-hop IP address. (Note: the next-hop is not used for determining changes.)

Output Format:

• Output a single integer: the number of times the route entry (identified by destination and mask length) selected for the target IP changes over the snapshots. The initial snapshot does not count as a change.

Example:

Consider the target IP 8.8.8.8 and the following 3 snapshots:

Snapshot 1:
4
0.0.0.0 /1 192.168.1.1
128.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
8.8.8.8 /32 192.168.1.253

Snapshot 2:
3
0.0.0.0 /1 192.168.1.1
128.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1

Snapshot 3:
3
0.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
8.8.8.8 /32 192.168.1.253

The best match in snapshot 1 is 8.8.8.8/32, in snapshot 2 it is 8.8.8.0/24, and in snapshot 3 it is again 8.8.8.8/32. Thus, there are 2 changes (snapshot 2 differs from snapshot 1, and snapshot 3 differs from snapshot 2).

inputFormat

The input begins with a line containing the target IP address. The next line contains an integer T, the number of snapshots. For each snapshot, the first line is an integer N (the number of route entries), followed by N lines each containing three fields separated by spaces: destination IP, mask length (with a preceding '/' character), and next-hop IP address.

For example:

8.8.8.8
3
4
0.0.0.0 /1 192.168.1.1
128.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
8.8.8.8 /32 192.168.1.253
...

outputFormat

Output a single integer, which is the count of route entry changes for the target IP (changes of the most specific matching route across snapshots). If no route matches in a snapshot, consider the best route as null.

sample

8.8.8.8
3
4
0.0.0.0 /1 192.168.1.1
128.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
8.8.8.8 /32 192.168.1.253
3
0.0.0.0 /1 192.168.1.1
128.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
3
0.0.0.0 /1 192.168.1.1
8.8.8.0 /24 192.168.1.1
8.8.8.8 /32 192.168.1.253

2