Efficient Algotithms 2022

As a world-renowned computer scientist, you have received an offer from a start-up Swiss bank to write some software for ATMs. Your program has to check if it is able to withdraw the amount requested by the customer with the available banknotes.

Input

The first line contains the number D, indicating the number of data sets. Each data set fits on one line and consists of six numbers: a1, a2, a3, a4, a5, k (ai ≤ 1000, k ≤ 10000). Numbers a1 - a5 denote the number of 10, 20, 50, 100, 200 Swiss franc banknotes available in the ATM. The number k indicates the desired amount to be withdrawn.

Output

For each data set, one line should appear in the result containing the single word TAK (yes) or NIE (no) indicating whether the ATM can currently supply the requested amount.

Example

Input:
3
0 2 10 10 1000 110
1 2 10 10 1000 110
199 100 40 20 10 10000

Output:
NIE
TAK
NIE