Logic gate is one of the important components in digital system. There are different types of gates. One of the interesting things is that whatever the type of the gate is the input combination will be the same. The output combination differs from gate to gate. For example let us consider the following gates.

On the above example the input combination (A, B, C) are the same. The output combinations differs (here X is the output).

As a programmer write a program that will take number of input variables as input and show their input combinations as output.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

For each test case, program takes one integer N (1 ≤ N ≤ 3) that means total number of input for a particular gate.

Output

For each test case, print the case number and input combinations as output.

Example

Input:
2
2
3

Output:
Case 1:
00
01
10
11
Case 2:
000
001
010
011
100
101
110
111

Problem setter: Saifur Rahman , Assistant Professor Department of CSE, Bangladesh University of Business and Technology (BUBT)