Arthur was the first born son of King Uther Pendragon and heir to the throne. However these were very troubled times and Merlin, a wise magician, advised that the baby Arthur should be raised in a secret place and that none should know his true identity.

As Merlin feared, when King Uther died there was great conflict over who should be the next king. Merlin used his magic to set a sword in a stone. Written on the sword, in letters of gold, were these words: ”Whoso pulleth out this sword of this stone is the rightwise born king of all England.” Of course all the contenders for the throne took their turn at trying to draw the sword, but none could succeed. Arthur, quite by chance, withdrew the sword for another to use in a tournament. Following this he became King.

As few knows, how he found his knights is a mystery. After reading Merlin’s scroll, the secret is to find the knight with the implicit knight number tattoo.

A knight number is a number whose digits are composed of 4 or 7. 47774 and 7 are knight numbers, but 28, 700, and 728 are not knight numbers. An implicit knight number is divisible by a knight number. 28, 728, and 700 are implicit knight numbers. Check whether the number is an implicit knight number or not. 

The first line contains an integer T (T ≤ 100), which indicates the number of test cases. For each case, the first line is a non-negative integer N (N ≤ 1015). 

For each case, output one line containing a character ”T”(True) / ”F”(False) denoting whether the number is an implicit knight number.