• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

پوریا در حال ساختن پایگاه خودش در بازی Terraria است. پایگاه او زیر زمین است و نقشه‌ی زمین بالای پایگاه به شکل یک جدول با \(n\) سطر و \(m\) ستون داده شده که هر خانه یا خالی (.) است یا مانع (#).

پوریا می‌خواهد از بالای نقشه به پایین آن یک مسیر بسازد. مسیر باید در یکی از خانه‌های خالی سطر اول شروع شود و در یکی از خانه‌های خالی سطر آخر تمام شود. با شروع از خانه ای در سطر اول در هر مرحله می‌توان از یک خانه به یک خانه‌ی مجاور ضلعی اش حرکت کرد در صورتی که حرکت به جهت پایین، چپ یا راست باشد و از جدول خارج نشویم. حرکت رو به بالا مجاز نیست چون پوریا بر این باور است که برای رسیدن به پایگاه اتلاف انرژیست. همچنین مسیر نمی‌تواند از داخل مانع (#) یا خانه‌ای تکراری عبور کند.

به این ترتیب، ممکن است چند مسیر مختلف از بالا به پایین وجود داشته باشد. ما «پیچیدگی» نقشه را برابر با تعداد این مسیرها تعریف می‌کنیم. پوریا دوست دارد نقشه‌اش پیچیدگی دقیقاً برابر با ۱ داشته باشد: یعنی دقیقاً یک مسیر یکتا از بالا به پایین وجود داشته باشد.

وظیفه‌ی شما این است که برای هر خانه بررسی کنید اگر مقدار آن خانه را برعکس کنیم (یعنی . را به # یا # را به . تغییر دهیم) آیا پیچیدگی جدول جدید دقیقاً برابر با ۱ می‌شود یا نه.

ورودی

خط اوّل شامل یک عدد صحیح \(t\) است — تعداد تست‌ها.
\[ 1 \leq t \leq 10^5 \]

خط اول هر تست شامل دو عدد صحیح \(n\) و \(m\) است — تعداد سطرها و ستون‌های جدول.

\[ 1 \le n, m \le 10^6,\; n \cdot m \le 10^6 \]

سپس \(n\) خط می‌آید که هرکدام دقیقاً شامل \(m\) کاراکتر . یا # است و وضعیت جدول را توصیف می‌کند.

تضمین می‌شود که مجموع \(n \cdot m\) روی تمام تست‌ها از \(10^6\) بیشتر نمی‌شود.

خروجی

برای هر تست یک جدول \(n \times m\) چاپ کنید. در سطر \(i\) از خروجی، باید دقیقاً \(m\) کاراکتر بدون فاصله چاپ شود. کاراکتر مربوط به خانه‌ی \((i,\ j)\) باید 1 باشد اگر با تغییر همان خانه پیچیدگی دقیقاً برابر با ۱ می‌شود، و 0 در غیر این صورت.

مثال

ورودی نمونه ۱

3
4 4
##.#
...#
.#.#
.#.#
5 5
##.##
...##
.##..
..##.
#.###
3 1
.
#
.

خروجی نمونه ۱

0000
1100
1010
1010
00001
00011
00111
00111
00011
0
1
0