URI Online Judge | 1784

Birds vs Crows

By Gustavo Stor, UFPE BR Brazil

Timelimit: 1

There are N birds in a forest, each in their respective tree. There are N tired crows in this forest, and they wish to land in different trees as soon as possible (crows are extremely quarrelsome and they can't share the same tree). Every Pi minutes, the i-th bird leaves the tree to fly a little bit, and you can consider that it returns immediately. Every Ci minutes, the i-th crow can try to land in a tree which there's no bird or can just keep flying. You can consider that crows are faster than birds and if the bird leaves the tree at the same minute that a crow tries to land in it, the crow will land faster. Given an optimal strategy between the crows, what is the earliest time in which every crow will be relaxing, each one in a different tree?

Input

The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases. Each test case starts with an integer N (1 ≤ N ≤ 9), the number of birds and crows. The second line contains N integers Pi (1 ≤ Pi ≤ 10⁴), as described in the problem statement. The third and last line of each test case contains N integers Ci (1 ≤ Ci ≤ 10⁴), as also described in the problem statement.

Output

For each test case print “Caso #X: Y”, where X is the number of the current case, starting at 1, and Y is the answer to the problem.

Input Sample Output Sample

2
2
1 3
2 2
1
1
1

Caso #1: 6
Caso #2: 1