It's a hot summer day they said in the news, the only thing Jimmy wants is to get outside and play with his friends, but with the actual weather is really hard to play without getting thirsty fast. So Jimmy thought he should bring some water, but how much water should Jimmy bring?

Also, Jimmy is not an ordinary boy, he can see the future. However, he can't watch how much water each of his friends is going to drink, but he can calculate it in base of how much distance they are going to run.

Jimmy already knows F of his friends are coming to play with him. He also knows his i-th friend is going to move M_i times and they will end their j-th movement at a position (x_ij, y_ij).

Jimmy is also really smart, so he figured out that for each 100 meters one of his friends run, he must bring 1 liter of water.

Given the information provided by Jimmy, can you calculate how much water should Jimmy bring?

Input

The first line consists of an integer T representing the number of test cases. T test cases follow.

Each case starts with a line containing the number of friends F. For each friend, (M_i+2) lines follow, where the first of these lines contains the integer M_i. The next (M_i+1) lines show the end positions for the movements the friend is going to do given by the two integers x_ij and y_ij. Keep in mind that the position x_i0 and y_i0 represent their starting points.

Output

For each case, it should be printed "Scenario #i: " followed by an integer equal to the ceiling of the amount of water Jimmy should bring.

Example

Input:
2
2
2
0 0
100 0
100 100
1
200 50
100 50
2
2
5 10
100 5
0 10
3
0 50
100 100
0 0
-100 -100

Output:
Scenario #1: 3
Scenario #2: 6

Constraints

Subtask 1 (40%):

• T <= 10
• F, M_i <= 100
• x_ij, y_ij are integers
• -100 <= x_ij, y_ij <= 100

Subtask 2 (60%):

• T <= 10
• F, M_i <= 100
• x_ij, y_ij are integers
• -1000000 <= x_ij, y_ij <= 1000000