You live in the universe X where all the physical laws and constants are different from ours. For example all of their objects are N-dimensional. The living beings of the universe X want to build an N-dimensional monument. We can consider this N dimensional monument as an N-dimensional hyper-box, which can be divided into some N dimensional hypercells. The length of each of the sides of a hyper-cell is one. They will use some N-dimensional bricks (or hyper-bricks) to build this monument. But the length of each of the N sides of a brick cannot be anything other than fibonacci numbers. A fibonacci sequence is given below:
1, 2, 3, 5, 8, 13, 21...
As you can see each value starting from 3 is the sum of previous 2 values. So for N = 3 they can use bricks of sizes (2,5,3), (5,2,2) etc. but they cannot use bricks of size (1,2,4) because the length 4 is not a fibonacci number. Now given the length of each of the dimension of the monument determine the minimum number of hyper-bricks required to build the monument. No two hyper-bricks should intersect with each other or should not go out of the hyper-box region of the monument. Also none of the hyper-cells of the monument should be empty.
First line of the input file is an integer T (1<=T<=100) which denotes the number of test cases. Each test case starts with a line containing N (1<=N<=15) that denotes the dimension of the monument and the bricks. Next line contains N integers the length in each dimension. Each of these integers will be between 1 and 2000000000 inclusive.
For each test case output contains a line in the format 'Case x: M' where x is the case number (starting from 1) and M is the minimum number of hyper-bricks required to build the monument.
2 2 4 4 3 5 7 8
Case 1: 4 Case 2: 2
Migrated from old NTUJ.
Regional Dhaka 2010
| No. | Testdata Range | Score |
|---|