SPOJ Brasil

Tjalling C. Koopmans ganhou em 1975 o prêmio Nobel de Economia juntamente com o matemático russo Kantorovich pelas suas contribuições em importantes áreas como a alocação ótima de recursos. Koopmans formou-se em Matemática pela Universidade de Utrecht, na Holanda, e se especializou em economia matemática. Durante a segunda guerra mundial esteve envolvido no estudo de alocação ótima de recursos, que 30 anos mais tarde lhe rendeu o prêmio Nobel. É considerado um dos precursores da teoria de programação linear. Suas contribuições têm importantes aplicações em Economia, Matemática, Física e mesmo em Química.

Um dos problemas prediletos de Koopmans era o de alocação ótima de commodities. Neste problema, é dado um valor inicial e um valor final da aplicação a ser feita. Entretanto, nem todos os valores podem ser aplicados nos vários investimentos. Cada investimento é definido através de um número inteiro, e, por convenção, apenas quando o valor a ser aplicado for um múltiplo de pelo menos um número que define um investimento ele pode ser aplicado.

Sua tarefa neste problema é calcular o valor máximo que pode ser aplicado. Ou seja, dado o valor inicial e valor final a serem aplicados e uma lista de inteiros que definem as várias aplicações, você deverá calcular a soma dos valores que podem ser aplicados no intervalo.

Entrada

A primeira linha de um caso de testes indica o número de instâncias subsequentes. A primeira linha de cada instância possui três inteiros I, F e N (1 ≤ I ≤ F ≤ 1000000000 e 1 ≤ N ≤ 20) que representam o valor inicial, o valor final e o número de elementos da lista de aplicações. A próxima linha contém N inteiros 1 ≤ a_i ≤ 1000000000 indicando a lista de aplicações.

Saída

Para cada instância imprima uma linha contendo a soma dos valores que podem ser aplicados no intervalo. Como este valor pode ser muito grande então imprima o resultado módulo 1300031.

Exemplo de entrada
3
1 10 1
1
1 9 2
3
5
1 999 2
3
5

Exemplo de saída
55
23
233168