牛牛有一个由 共 个整数组成的环。 牛妹对这个数环进行了 次询问，每次给定一个整数 问牛牛操作到不能继续操作时最少会剩下几个数。 每一次操作，牛牛都会选择环上一段（可以是整个环），这一段数的和应该为 的倍数，然后牛牛就会删去这一段，同时把剩下的数按顺序重新连成一个环。

输入描述:

本题采用多组案例输入，第一行一个整数  代表案例组数。每组案例中，第一行输入两个空格分隔的整数： 。接下来一行输入一个整数  。接下来  行，每行输入一个数  代表询问。保证：单个测试点中所有案例 的和不超过

输出描述:

对于每组案例，输出共 行，每行一个整数代表牛妹询问的答案。