SPOJ Brasil

A Absolute CoMputers (ACM) é uma grande companhia da área de informática. Criando tanto aplicativos de larga escala, como sistemas gerenciadores de banco de dados, quanto sistemas de controle de estoque, a empresa vinha crescendo a cada ano em percentuais impressionantes. Isso até seu último lançamento, quando prometeram algo totalmente inovador: a possibilidade do usuário de ter uma calculadora no seu próprio computador. “Não há nada de novo nisso!”, você pode pensar. Mas se o fez é só porque não me deixou terminar de explicar tudo. Senta aí e termina de ler tudo primeiro!

Uma das novas features dessa calculadora é que todas as operações podem ser definidas através de um script. Ou seja, você pode criar desde simples somatórias até complicadas equações diferenciais que a calculadora fará as contas e lhe dará o resultado correto. Para demonstrar o poder da linguagem de script a ACM fez uma apresentação em um evento internacional. Nessa apresentação iria exibir exemplos de utilizações avançadas da calculadora ao público.

Inicialmente o encarregado para o desenvolvimento dos complexos scripts seria o diretor de projeto. Porém ele resolveu tirar férias algumas semanas antes do evento, e passou a tarefa para o chefe de desenvolvimento. Esse, muito ocupado com seus jogos de golfe, repassou para o desenvolvedor sênior. Como o desenvolvedor sênior estava com muitos bugs (em outros projetos) para corrigir, repassou para o programador júnior. Já o programador júnior achou que aquilo era só mais um trote, e resolveu aproveitar a “piada” para aprontar com o estagiário. Aí o estagiário fez o que sabe de melhor (vocês já sabem o quê). Resultado: o que era para ser um script complexo para demonstrar o poderio do software tornou-se em um simples exemplo de potenciação. E pior, com três falhas grotescas:

1. o único número aceito como base da potência era 1331
2. a base numérica era 1300031
3. e ele esqueceu totalmente do “vai um”. Segue abaixo um exemplo de multiplicação (na base 16) com esse bug.

     4  5
×    3  1
---------
     4  5
+ 12 15
---------
  12 3  5

Mas nem tudo foi perdido. Meu professor adorou esse novo tipo de operação e passou como tarefa simulá-la. Como não tenho um estagiário, vai ter que ser você mesmo para me ajudar.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância terá uma linha com dois inteiros N e P.

Restrições

1 <= N <= 10000
0 <= P <= 100

Saída

Para cada instância, imprima o valor, computado pelo script do estagiário, do P-ésimo dígito (começando em 0 — da direita para esquerda) de 1331 elevado a N.

Exemplo de entrada

3
1 1
2 0
2 5

Saída para o exemplo de entrada

3
1
6

Comentários

A culpa não é do estagiário! A culpa é do Carlinhos! :–)