Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMHCN - Đếm hình chữ nhật

Bạn được cho một bảng hình chữ nhật kích thước R*C:

  • Trên bảng có một số khung hình chữ nhật rỗng (chỉ gồm 4 cạnh của hình chữ nhật).
  • Các khung hình chữ nhật có thể lồng nhau, nhưng không có 2 khung hình chữ nhật nào chạm nhau (nghĩa là không có ô nào của bảng thuộc nhiều hơn 1 khung hình chữ nhật, và không có 2 ô chung cạnh hay chung đỉnh thuộc 2 khung hình chữ nhật khác nhau). Nói cách khác, hai hình chữ nhật lồng nhau có nghĩa là một hình chữ nhật này nằm hoàn toàn bên trong một hình chữ nhật kia.
  • Mỗi ô trên bảng là 'o' hoặc '.'. Ký tự 'o' thể hiện ô đó thuộc một khung hình chữ nhật và ký tự '.' thể hiện ô đó không thuộc bất kỳ khung hình chữ nhật nào. 

Bạn cần tìm dãy dài nhất các hình chữ nhật A(1), ..., A(k) mà A(1) nằm trong A(2), A(2) nằm trong A(3), ... Ai nằm trong A(i+1), ... A(k-1) nằm trong A(k)

Input

Dòng 1: số nguyên dương T - số lượng test

Tiếp theo là T test, mỗi test gồm:

  • Dòng đầu: 2 số nguyên dương R và C
  • Tiếp theo là R dòng, mỗi dòng gồm C ký tự. Mỗi ký tự là 'o' hoặc '.'

Output

Gồm T dòng, mỗi dòng một số nguyên duy nhất là kết quả của bài toán

Giới hạn

  • R, C <= 2000
  • Không có khung hình chữ nhật nào nhỏ hơn 3x3.

Example

Input:
1
8 11
ooooooo....
o.....o.ooo
o.ooo.o.o.o
o.o.o.o.ooo
o.ooo.o....
o.....o.ooo
ooooooo.o.o
........ooo
Output:
2

Được gửi lên bởi:VOJ Team
Ngày:2014-07-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VM14 - RR

hide comments
2014-08-04 10:05:35 Lollipop
nếu k tìm đk cái thứ 2 thì in ra 1 à
2014-07-30 14:41:40 Chuyên Nhật CNN
o_O O((R*C div 25)^2) đc 85 điểm :v
2014-07-30 08:10:21 ∞Skyscraper∞
Cái dk thứ 2 là test tm luôn hay phải ktra lại ạ ???
2014-07-30 03:04:40 Lollipop
đề bài này khó hiểu quá @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.