시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 7 7 100.000%

문제

아래 다면체는 1x1x1 정육면체로 만들어져있다. 이 문제에서는 블록이 땅에 닿지 않고 공중에 떠있는 경우는 고려하지않는다(각 칸에는 한개 이상의 정육면체가 차곡차곡 쌓아 올려져있다). 이런 다면체는 숫자들의 행렬로써 주어지며,  각각의 숫자는 각 칸에 쌓아 올려진 정육면체의 수를 의미한다. 0의 경우, 해당 칸에 쌓여진 블록이 없음을 의미한다.

해당하는 그림의 행렬은 아래와 같다.

4231
2101
0001 

주어진 행렬로부터 바닥을 포함한 이러한 다면체의 면적을 구하라. 주어진 다면체를 이루는 정육면체들은 모두 맞닿아 있으며, 동떨어진 블록은 없다.

입력

첫째 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫째 줄에는 행렬의 행과 열의 크기인 R과 C(1≤R, C≤50)가 주어진다. 그 다음 줄부터는 차례로 R번째 줄마다 C개의 수가 주어진다. 각 숫자의 크기는 0이상 9이하이다.

출력

각 줄마다 테스트케이스에 주어진 다면체의 면적을 출력하라.

예제 입력 1

4
1 2
11
3 4
4231
2101
0001
3 3
111
101
111
1 1
5

예제 출력 1

10
54
32
22
W3sicHJvYmxlbV9pZCI6Ijk3MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhNzRcdWM4MDEgXHVhZDZjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDRcdWI3OTggXHViMmU0XHViYTc0XHVjY2I0XHViMjk0IDF4MXgxIFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4MzhcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViZTE0XHViODVkXHVjNzc0IFx1YjU0NVx1YzVkMCBcdWIyZmZcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YWNmNVx1YzkxMVx1YzVkMCBcdWI1YTBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMFx1YzU0YVx1YjI5NFx1YjJlNChcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IFx1ZDU1Y1x1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVhYzAwIFx1Y2MyOFx1YWNlMVx1Y2MyOFx1YWNlMSBcdWMzMTNcdWM1NDQgXHVjNjJjXHViODI0XHVjODM4XHVjNzg4XHViMmU0KS4gXHVjNzc0XHViN2YwIFx1YjJlNFx1YmE3NFx1Y2NiNFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NTggXHVkNTg5XHViODJjXHViODVjXHVjMzY4IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgJm5ic3A7XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzMxM1x1YzU0NCBcdWM2MmNcdWI4MjRcdWM5YzQgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIDBcdWM3NTggXHVhY2JkXHVjNmIwLCBcdWQ1NzRcdWIyZjkgXHVjZTc4XHVjNWQwIFx1YzMxM1x1YzVlY1x1YzljNCBcdWJlMTRcdWI4NWRcdWM3NzQgXHVjNWM2XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvOTcxNVwvJUVDJThBJUE0JUVEJTgxJUFDJUVCJUE2JUIwJUVDJTgzJUI3JTIwMjAxNi0xMC0wNCUyMCVFQyU5OCVBNCVFRCU5QiU4NCUyMDQuMDMuMzMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQxcHg7IHdpZHRoOjE5MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI5YmNcdWM3NTggXHVkNTg5XHViODJjXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjQyMzE8YnIgXC8+XHJcbjIxMDE8YnIgXC8+XHJcbjAwMDEmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU4OVx1YjgyY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCZuYnNwO1x1YmMxNFx1YjJlNVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWMgXHVjNzc0XHViN2VjXHVkNTVjIFx1YjJlNFx1YmE3NFx1Y2NiNFx1Yzc1OCBcdWJhNzRcdWM4MDFcdWM3NDQgXHVhZDZjXHVkNTU4XHViNzdjLiBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU0XHViYTc0XHVjY2I0XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YjlkZVx1YjJmZlx1YzU0NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjNkOVx1YjVhOFx1YzViNFx1YzljNCBcdWJlMTRcdWI4NWRcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3OCBSXHVhY2ZjIEMoMSZsZTtSLCBDJmxlOzUwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyBSXHViYzg4XHVjOWY4IFx1YzkwNFx1YjljOFx1YjJlNCBDXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDBcdWM3NzRcdWMwYzEgOVx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU0XHViYTc0XHVjY2I0XHVjNzU4IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTcxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1cmZhY2UgQXJlYSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHNvbGlkIGluIHRoZSBwaWN0dXJlIGJlbG93IGlzIG1hZGUgdXAgb2YgMXgxeDEgY3ViZXMgaW4gYSAzRCBncmlkLiBJbiB0aGlzIHByb2JsZW0sIHdlJiMzOTtsbCBsaW1pdCBvdXJzZWx2ZXMgdG8gc29saWRzIHRoYXQgYXJlIG1hZGUgdXAgb2YgY29sdW1ucyByb290ZWQgb24gdGhlIGdyb3VuZCAoYSBjb2x1bW4gY29uc2lzdHMgb2Ygb25lIG9yIHNldmVyYWwgMXgxeDEgY3ViZXMgc3RhY2tlZCBvbiB0b3Agb2YgZWFjaCBvdGhlcikuIFN1Y2ggc29saWRzIGNhbiBiZSBkZXNjcmliZWQgYXMgYSBtYXRyaXggb2YgZGlnaXRzLCB3aGVyZSBlYWNoIGRpZ2l0IGNvcnJlc3BvbmRzIHRvIHRoZSBoZWlnaHQgb2YgYSBjb2x1bW4gaW4gdGhlIDJEIGdyaWQgdGhhdCBtYWtlcyB1cCB0aGUgZ3JvdW5kLiBBIHplcm8gbWVhbnMgdGhlcmUgaXMgbm8gY29sdW1uIGF0IGFsbCBpbiB0aGF0IHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC85NzE1XC8lRUMlOEElQTQlRUQlODElQUMlRUIlQTYlQjAlRUMlODMlQjclMjAyMDE2LTEwLTA0JTIwJUVDJTk4JUE0JUVEJTlCJTg0JTIwNC4wMy4zMy5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDFweDsgd2lkdGg6MTkwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGNvcnJlc3BvbmRpbmcgbWF0cml4IGZvciB0aGUgYWJvdmUgc29saWQgd2lsbCBiZSAmbmJzcDs8XC9wPlxyXG5cclxuPHA+NDIzMTxiciBcLz5cclxuMjEwMTxiciBcLz5cclxuMDAwMTxcL3A+XHJcblxyXG48cD5UaGUgdm9sdW1lIG9mIHN1Y2ggYSBzb2xpZCBpcyBzaW1wbGUgZW5vdWdoIHRvIGNhbGN1bGF0ZSwgYnV0IHdoYXQgd2UmIzM5O3JlIGludGVyZXN0ZWQgaGVyZSBpbiB0aGUgdG90YWwgc3VyZmFjZSBhcmVhIGluY2x1ZGluZyB0aGUgZmxvb3IgKHRoYXQgaXMsIHRoZSBudW1iZXIgb2YgMXgxICZxdW90O3NxdWFyZXMmcXVvdDsgbm9uIGhpZGRlbiBvbiB0aGUgb3V0ZXIgc3VyZmFjZSkuIFlvdSBhcmUgZ2l2ZW4gdGhlIGluZm9ybWF0aW9uIG9mIHRoZSBzb2xpZCBhcyBhIG1hdHJpeC4gWW91ciB0YXNrIGlzIHRvIGNvbXB1dGUgdGhlIHN1cmZhY2UgYXJlYSBvZiB0aGUgZ2l2ZW4gc29saWQuIFlvdSBjYW4gYXNzdW1lIHRoYXQgdGhlIHNvbGlkIGlzIGFsd2F5cyBjb25uZWN0ZWQsIGkuZSB0aGUgY29sdW1ucyB3aWxsIGJlIGF0dGFjaGVkIHRvIGVhY2ggb3RoZXIgaW4gdGhlIGZvdXIgY2FyZGluYWwgZGlyZWN0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIFQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gJm5ic3A7RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgUiBhbmQgQyBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIHNvbGlkLiBFYWNoIG9mIHRoZSBuZXh0IFIgbGluZXMgY29udGFpbnMgQyBkaWdpdHMuIEVhY2ggZGlnaXRzIGFyZSBiZXR3ZWVuIDAgdG8gOSBpbmNsdXNpdmUuIFIgYW5kIEMgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDUwIGluY2x1c2l2ZS4gJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHRvdGFsIHN1cmZhY2UgYXJlYSBvZiB0aGUgZ2l2ZW4gc29saWQsIGluY2x1ZGluZyB0aGUgZmxvb3IgYXJlYS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=