SP2004X - Bankomat

no tags 

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

hide comments
XLk: 2024-07-15 09:04:44

1
0 5 2 0 0 130
TAK

smso: 2024-05-29 17:03:47

WA if max k = 10000. Increase max k to 100000 to pass.


Added by:Rafał Witkowski
Date:2022-05-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:sparing 8.05.2004 (PP), Władysław Bodzek