Problema E: Shallow fake sunflower


image Van_gogh

Nas redes sociais humanas proliferam as deep fakes. Nas dos girassóis o problema ainda são as falsificações grosseiras (shallow fakes) de fotografias de girassóis famosos. A imagem da direita é de um quadro de van Gogh.

Felizmente os hackers parecem ignorar algo importante sobre a disposição das sementes de girassol no centro das flores.

As sementes estão alinhadas em espirais, umas que evoluem a partir do centro no sentido horário (a verde na figura em baixo, à esquerda) e outras no sentido contrário (a vermelho na figura em baixo, à direita). E há uma relação entre o número de espirais nos dois sentidos: são sempre dois números consecutivos na sequência de Fibonacci! No exemplo ilustrado nas figuras, há 55 espirais no sentido horário e 34 espirais no sentido anti-horário.

image left image right
A sequência de Fibonacci começa pelos números 0 e 1; ou seja, F0=0 e F1=1. Os valores seguintes da sequência são dados pela fórmula recursiva Fn=Fn−1+Fn−2 (i.e., para n≥2, o valor de Fn corresponde à soma dos dois valores anteriores). Os primeiros valores da sequência são os seguintes: 
                        0   1   1   2   3   5   8   13   21   34   55   …

Tarefa

A GiraMeta - a empresa que controla as principais redes sociais de girassóis - contratou-nos para desenvolver um programa que deteta shallow fakes nas fotografias publicadas. Já temos o módulo que conta o número de espirais em cada um dos sentidos - horário e anti-horário. Alguns girassóis são transgénicos e têm imensas espirais! Precisamos agora de um programa que determine quais são os pares que correspondem a girassóis verdadeiros. Ou seja, cujos números de espirais em cada sentido são números consecutivos da sequência de Fibonacci.

Input

A primeira linha do input contém um inteiro, N, que é o número de fotografias a analisar. Seguem-se N linhas, cada uma com dois inteiros, A e B, que indicam os números de espirais em sentido horário e anti-horário da fotografia de um girassol.

Restrições

  1≤N≤200 Número de fotografias
  0≤A≤20000 Número de espirais no sentido horário de uma fotografia
  0≤B≤20000 Número de espirais no sentido anti-horário de uma fotografia

Output

O output tem uma linha por cada fotografia, pela ordem definida no input. Cada linha tem uma palavra, que classifica os valores correspondentes do input. Essa palavra é: "OK" (sem aspas), se os dois valores forem números consecutivos da sequência de Fibonacci; "FAKE" (sem aspas), no caso contrário. De notar que os valores não têm que estar por ordem crescente para serem números consecutivos da sequência de Fibonacci.

Exemplo 1

Input 

3
1 1
3 5
2 5

Output 

OK
OK
FAKE

Exemplo 2

Input 

7
13 21
13 22
21 13
34 13
34 21
21 21
21 34

Output 

OK
FAKE
OK
FAKE
OK
FAKE
OK


ToPAS'2022
193.136.122.94