Background

Special for beginners, ^_^

Description

输入两个整数a和b(都不超过1e11)，比较他们的阶乘%123456789的大小。

Format

Input

第一行给出一个整数T，表示有T组数据（T<=1000）。 后面每行一组两个数，分别为a和b。.

Output

比较(a!)%123456789和(b!)%123456789的大小。 如果第一项大，则输出a。 如果第二项大，则输出b。 如果两个大小一样，则输出tie。

Samples

3
2 1
1 2
2 2

a
b
tie

Limitation

1s, 1024KiB for each test case.