Cô gái chăn bò

View as PDF
Submit solution
Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Thank to Nguyễn Trần Nam Khánh and Nguyễn Hoàng Nghĩa
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên một thảo nguyên nhỏ bé có ~1~ gia đình gồm ~3~ anh em: ~2~ người anh trai là Nvutri và Andorea còn người em gái là Lola. Cuộc sống gia đình khá giả nhưng gia đình có truyền thống chăn nuôi và muốn để các con tự lập nên cha mẹ ~3~ người quyết định để các con hằng ngày sẽ đi chăn một số bò nào đó (tùy ý ~3~ người con).

Thảo nguyên là ~1~ cánh đồng chia làm ~M \times N~ ô vuông, mỗi con bò chỉ đứng trong ~1~ ô và mỗi ô chỉ chứa ~1~ con bò. Chỉ có ~1~ quy tắc duy nhất là không bao giờ được để ~4~ con bò tạo thành ~1~ hình vuông ~2 \times 2~ hoặc để trống ~1~ khu đất ~2 \times 2~.

Hai người anh mải chơi nên đã hối lộ kem để Lola chăn bò ~1~ mình. Lola muốn biết tất cả có bao nhiêu cách xếp bò thỏa mãn quy tắc trên để đề phòng mọi trường hợp. Vì con số này rất lớn nên hãy giúp Lola tính toán con số này.

Input

Dòng đầu gồm ~1~ số T duy nhất là số test ~(T \le 111)~.

~T~ dòng tiếp theo gồm ~2~ số ~M~, ~N~ cho biết kích thước của thảo nguyên ~(M \times N \le 30)~.

Output

Gồm ~T~ dòng, mỗi dòng ứng với ~1~ test là số cách xếp bò của test đó.

Sample Input

1
1 1

Sample Output

2

Comments

Please read the guidelines before commenting.


  • -15
    doquangnghia_20222025  commented on April 14, 2024, 2:27 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -24
    l1i3nh  commented on June 28, 2023, 2:27 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -39
    Thanh22Ti  commented on March 30, 2023, 8:53 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -39
    Thanh22Ti  commented on March 30, 2023, 8:52 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -39
    Thanh22Ti  commented on March 30, 2023, 8:52 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -37
    ducdacoder3103  commented on March 30, 2023, 8:39 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -38
    ducdacoder3103  commented on March 30, 2023, 8:39 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -38
    kripper  commented on March 30, 2023, 7:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -38
    kripper  commented on March 30, 2023, 7:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -38
    kripper  commented on March 30, 2023, 7:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -38
    kripper  commented on March 30, 2023, 7:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -37
    kripper  commented on March 30, 2023, 7:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -45
    nasam  commented on March 30, 2023, 7:48 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -47
    kripper  commented on March 30, 2023, 7:47 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.