小苯有一个长度为 的序列 ，但小苯现在只对合数感兴趣，因此小苯希望 中所有的元素都是合数。 为此，小苯可以做如下的操作任意次： 选择一对相邻的数字，将他们合并成一个数，结果为两者的积。 （形式化的：选择 ，将 和 合并为一个数字，结果是 。 小苯想知道，如果要满足他的条件（即所有元素都是合数），则在他操作完后， 有多少种可能的形态，请你帮他算一算吧。 （小苯认为两个序列 的最终形态不同，当且仅当两个序列 的长度不同、或者长度相同且存在 使得 。）

输入描述:

本题有多组测试数据。输入的第一行包含一个正整数 ，表示数据组数。接下来包含 组数据，每组数据的格式如下：第一行一个正整数 ，表示序列 的长度。第二行 个正整数 ，表示序列 。（保证所有测试数据中， 的总和不超过 ）

输出描述:

对于每组测试数据：在单独的一行输出一个整数，表示最终符合条件的 的可能结果。特别的，如果无论如何操作都无法满足小苯的条件则输出 。（由于结果可能很大，因此你只需要输出结果对 取模的值即可。）