12.นกน้อย
คำโบราณว่าไว้ "นกน้อยทำรังแต่พอตัว"
สำหรับโจทย์ข้อนี้ นกจะมีขนาดเป็นจำนวนเต็มและทำรังบนพื้นที่ที่มีลักษณะเป็นตาราง นกขนาดต่าง ๆ จะต้องการพื้นที่ทำรังขนาดแตกต่างกัน กล่าวคือ นกขนาด i จะต้องการพื้นที่ทำรังมีลักษณะเป็นพื้นที่ข้าวหลามตัดกว้างและสูง 2i - 1 หน่วย ดังแสดงในตัวอย่างด้านล่าง
..... ..... ..#..
..... ..#.. .###.
..#.. .###. #####
..... ..#.. .###.
..... ..... ..#..

 (1)      (2)      (3)

รูปด้านบนแสดงลักษณะของพื้นที่ที่นกขนาด 1, 2, และ 3 ใช้ทำรัง ตามลำดับ ส่วนของช่องที่ใช้ทำรังแสดงด้วอักษร #
พื้นที่สนามที่นกจะทำรังมีขนาดกว้าง N หน่วยและสูง M หน่วย และแบ่งเป้นตารางย่อย ๆ ขนาด 1 x 1 หน่วย จำนวน NM ช่อง
ในพื้นที่ดังกล่าว มีบางช่องของตารางที่ไม่เหมาะต่อการทำรังของนก เช่น มีหลุม หรือมีรังแมลงป่องซ่อนอยู่ ดังนั้นในการสร้างรัง จะมีส่วนขอบพื้นที่รูปข้าวหลามตัดของรังนกทับช่องที่ไม่เหมาะสมไม่ได้
ให้คุณเขียนโปรแกรมรับขนาดของนก แล้วหาว่ามีตำแหน่งที่นกขนาดดังกล่าวสามารถทำรังในสนามได้กี่ตำแหน่ง
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม T แทนจำนวนชุดข้อมูลทดสอบ (1 <= T <= 10) จากนั้นจะข้อมูลจะตามด้วยชุดทดสอบ T ชุด โดยแต่ละชุดจะอยู่ในรูปแบบต่อไปนี้
บรรทัดแรกของข้อมูลชุดทดสอบจะระบุจำนวนเต็มสามจำนวน N M และ K (1 <= N <= 30; 1 <= M <= 30; 1 <= K <= 10) โดยที่ N และ M แทนความกว้างและสูงของพื้นที่ และ K แทนขนาดของนก รับประกันว่า 2K-1 <= N และ 2K-1 <= M
จากนั้นจะตามด้วยข้อมูลของสนามจำนวน M บรรทัด แต่ละบรรทัดเป็นสตริงความยาว N ตัวอักษร โดยจะมีตัวอักษรสองรูปแบบคือ . แทนช่องที่เหมาะสมต่อการทำรัง และ O (ตัวอักษรโอใหญ่) แทนช่องที่ไม่เหมาะสม
ข้อมูลส่งออก
มีทั้งสิ้น T บรรทัด แต่ละบรรทัดคือคำตอบของแต่ละข้อมูลชุดทดสอบ กล่าวคือแต่ละบรรทัดแทนจำนวนตำแหน่งที่นกสามารถทำรังได้
ตัวอย่าง
ข้อมูลนำเข้า
2
5 5 2
O.O.O
.....
O.O.O
.....
O.O.O
4 3 2
....
.O..
....
ข้อมูลส่งออก
4
0