Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1583
Binomial Filter

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

Problem B: Binomial Filter


A common approach to reduce video image noise (so as to increase the image quality) is casting binomial filter on the bitmap image. The binomial filter works as this:

Assume that the image is represented as an N * N matrix of integers between 0 and 255 (we only concern about the Y component of YUV image, the brightness). We define the original image to be I, and the filtered image to be I'. So a pixel on the original image is represented as I[x,y], a pixel on the filtered image is I'[x,y].

We define the filter matrix B as:

to do the binomial filter, we calculate the filtered image pixel as:

If the pixel is on the image border(top,bottom,left,right):

else:

The division is integer division, we ignore the fraction part.

Now your job is to implement the binomial filter algorithm.


Input

There are multiple tests. Each test begins with an integer N (1 <= N <= 500), the image size. The following are N * N integers, each within [0,255], the pixels of the original image.

The input terminates with N = 0. Do not process this case.


Output

For each test case, first print one line with "Case c:", c is the case number, starting from 1.

N lines follow, each containing N integers, seperated by one space (no space after the last integer!), which are the pixels of the filtered image.


Sample Input

3
1 2 3
4 5 6
7 8 9
4
1 1 1 1
1 100 100 1
1 100 100 1
1 1 1 1
0


Sample Output

Case 1:
1 2 3
4 5 6
7 8 9
Case 2:
1 1 1 1
1 56 56 1
1 56 56 1
1 1 1 1



Author: CHENG, Long
Source: Zhejiang University Local Contest 2003, Preliminary
Submit    Status