신용카드 번호 판별

신용카드 번호는 16자리 숫자다. 얼핏 보면 아무 숫자나 늘어놓은 것 같지만, 번호가 제대로 입력됐는지 확인하는 규칙이 그 안에 들어 있다. 그 규칙이 Luhn 공식이고, 내용은 다음과 같다.

1. 맨 오른쪽 자리부터 1번, 2번 순서로 센다. 홀수 번째 자리의 숫자는 그대로 두고, 짝수 번째 자리의 숫자는 2배로 만든다.
2. 2배로 만든 값이 10 이상이면 그 값의 각 자리 숫자를 더한 값으로 바꾼다.
3. 이렇게 얻은 16개 값을 모두 더한다.
4. 합이 10으로 나누어떨어지면 유효한 번호이고, 그렇지 않으면 유효하지 않은 번호다.

신용카드 번호가 여러 개 주어진다. 각 번호가 유효한지 판정하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 1000$)가 주어진다.

둘째 줄부터 $T$개의 줄에 걸쳐 신용카드 번호가 한 줄에 하나씩 주어진다. 각 번호는 16자리 숫자이고, 맨 앞자리가 0일 수도 있다.

각 신용카드 번호에 대해 유효하면 T를, 유효하지 않으면 F를 한 줄에 하나씩 출력한다.