String Power

All submissions for this problem are available.

ALICE and BOB are playing a game with strings. Both of them have a string of length N consisting of lower case characters only.  

A permutation of “abcdefghijklmnopqrstuvwxyz” is given in the input that defines the POWER of the characters (a-z). The position of the character starting from the left defines the POWER of a character. The position of the leftmost character is taken to be 0.

If a character is common to both the strings, it is destroyed. The powers of the leftout characters of each of the strings are added separately. If a character is repeated, then power of only one such character is added. Person with the string of HIGHER POWER wins.  

ALICE and BOB want to check if you are smart enough to declare the winner in advance!!
Are you ready? ;)

Input

The first line of the input contains an integer T, denoting the length of the conversation, and the string M, denoting a permutation of the string "abcdefghijklmnopqrstuvwxyz" which defines the power of characters. T and M are separated by exactly one space.
The description of T test cases follows.
In each of the test cases, FIRST line contains ALICE’s string and SECOND line contains BOB’s string.

Output

For each query, output on a separate line the winner of the game as “ALICE” or “BOB” and “TIE” in case of a tie.
Quotes for clarity only.
.

Constraints

• 1 ≤ T ≤ 30000
• SIze of each string <= 100

Example

Input:
3
wmbqkhasuftlcnerdzoxviypjg
jack
jill
dwarka
moksha
umytissv
hlovhsny

Output:
BOB
ALICE
TIE

Explanation

Example case 1. In the first case both the 'j' are cancelled out then the strength of alice's
string is (6+12+4) 22 and for bob's string is (21+11) 32 therefore BOB is the answer.

Example case 2.In the second test case one 'a' and 'k' are cancelled out the strength of alice's string is (6+16+15+0) 37 and for bob's string is (5+1+18+7) 31 therefore ALICE is the answer.

NOTE : Use fast Input Output.