Brain "Perfect" Scheme

Brain, an intelligent mouse who has undergone a significant genetic alteration, is an evil mastermind. He has an ever-lasting desire to take over the world with his "perfect" evil scheme¹. Brain has a good friend, Pinky, who is also a mutant mouse, but is not so intelligent when compared to Brain. However, Pinky is more open-minded, friendly, sensitive, and sweet, which makes him adorable.

For his new "perfect" evil scheme, Brain needs to compute N computational jobs in some servers (jobs are numbered from 1 to N). Each job i has to be executed strictly from start time s_i to ending time e_i in one machine continuously without any interruption. Of course, Brain can just use N servers to run each jobs independently to each other; however, this alternative is very costly and Brain is getting poor from preparing his previous world-domination scheme. Therefore, he wants to minimize the number of needed server to complete all his jobs.

To make the matter worse, apparently it takes some time for a server to switch from one job to another. If a server finishes job j_x, then to start job j_y it will need an intermission time t_x,y after job j_x completes. This is the time required by the server to clean up job j_x and load job j_y. In other word, job j_y can be run after job j_x if and only if e_x + t_x,y ≤ s_y.

For example, let there be 3 jobs

s1 =  3 and e1 =  6
s2 = 10 and e2 = 15
s3 = 16 and e3 = 20
t1,2 = 2,  t1,3 = 5
t2,1 = 0,  t2,3 = 3
t3,1 = 0,  t3,2 = 0

Server 1: j1, j2
Server 2: j3

Brain has instructed Pinky to solve this problem, i.e. to find the minimum number of required server to finish all the jobs. Unfortunately, Pinky is not very bright (a.k.a. stupid). He needs your help to solve Brain's problem. You're going to help him right? He's adorable! We can't help it.

¹ The quote on "perfect" actually means he often makes a small fatal mistake which causes the plan to completely fail. Hence, he has never actually succeeded in conquering the world... yet.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with one integer N (1 ≤ N ≤ 100) in a line. The next N lines each contains two integers s_i and e_i (1 ≤ s_i < e_i ≤ 10⁵) denoting the start time and ending time of job j_i respectively. The following N lines each contains N integers t_x,y (0 ≤ t_x,y ≤ 10⁵). The y^th integer on x^th line of this matrix denotes the intermission time from job j_x to job j_y. t_x,x will be 0 for all x.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the number of minimum server required to finish all the jobs.

3
3
3 6
10 15
16 20
0 2 5
0 0 3
0 0 0
4
8 10
4 7
12 15
1 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
8 10
4 7
12 15
1 4
0 50 50 50
50 0 50 50
50 50 0 50
50 50 50 0

Case #1: 2
Case #2: 1
Case #3: 4

Explanation for the 2^nd sample input.

We can execute all jobs in one machine.

Explanation for the 3^rd sample input.

The jobs are the same as 2^nd sample input, but now the intermission times are huge. Therefore, we need to run each job in separated server independently.