Generate interleavings of two strings in lexicographical order in Python

Question

How to generate interleavings of two strings in lexicograhical order in python?

I was able to generate interleavings, but not in lexicographical order.

The input given was,

Input :

2

nkb gl

bn zh

Expected output:

Case #1: glnkb gnkbl gnklb gnlkb ngkbl ngklb nglkb nkbgl nkgbl nkglb

Case #2: bnzh bzhn bznh zbhn zbnh zhbn

This is my code --

def interleave(A,B,ans,m,n,idx):
    if m == 0 and n == 0:
        print("".join(ans))
        return 
    if len(A)<=len(B):
        if m!=0:
            ans[idx]=A[0]
            interleave(A[1:],B,ans,m-1,n,idx+1)
        if n!=0:
            ans[idx]=B[0]
            interleave(A,B[1:],ans,m,n-1,idx+1)
    else:
        if n!=0:
            ans[idx]=B[0]
            interleave(A,B[1:],ans,m,n-1,idx+1)
        if m!=0:
            ans[idx]=A[0]
            interleave(A[1:],B,ans,m-1,n,idx+1)
t=int(input())
count=0
for i in range(t):
    count+=1
    print("Case #%d:"%count)
    A,B=input().split()
    m,n=len(A),len(B)
    ans=['']*(m+n)
    idx=0
    interleave(A,B,ans,m,n,idx)

Output of the code that I wrote was--

Case #1:
glnkb
gnlkb
gnkbl
gnklb
nkbgl
nkgbl
nkglb
nglkb
ngkbl
ngklb
Case #2:
bnzh
bznh
bzhn
zhbn
zbnh
zbhn

There is some problem in the logic. Please help me to figure it out.