Masala E

- Siz \( N \times M \times P \) o'lchamli uch o'lchamli panjaraga egasiz. Har bir katak \( (x, y, z) \) da bitta lampochka bor. Dastlab barcha lampochkalar o'chiq holatda.

Sizga \( K \) ta qadam beriladi. Har bir qadamda:

Panjaradan tasodifiy ravishda \( A \) katagi tanlanadi.
Panjaradan tasodifiy ravishda \( B \) katagi tanlanadi.
\( A = (x_1, y_1, z_1) \) va \( B = (x_2, y_2, z_2) \) bo'lsa, quyidagi shartni qanoatlantiruvchi barcha \( (x, y, z) \) kataklardagi lampochkalar holati almashtiriladi (yoniq bo'lsa o'chiriladi, o'chiq bo'lsa yoqiladi):

\( \min(x_1, x_2) \le x \le \max(x_1, x_2) \)
\( \min(y_1, y_2) \le y \le \max(y_1, y_2) \)
\( \min(z_1, z_2) \le z \le \max(z_1, z_2) \)

\( K \) qadam o'tgandan so'ng yoniq lampochkalarning kutilgan sonini toping.

Eslatma: \( A \) va \( B \) bir xil katak bo'lishi mumkin.

Birinchi qatorda butun son \( T \) — test holatlar soni kiritiladi.

Keyingi \( T \) ta qatorda to'rtta butun son \( N \), \( M \), \( P \) va \( K \) — panjaraning o'lchamlari va qadam soni beriladi.

\( 1 \le T \le 100 \)
\( 1 \le N, M, P \le 100\)
\( 0 \le K \le 10^4 \)

Har bir test holat uchun bitta qatorda yoniq lampochkalarning kutilgan sonini chop eting. Javob \( 10^{-6} \) xatolikkacha qabul qilinadi.