{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"众所周知zhu是一个大厨,zhu一直有自己独特的咸鱼制作技巧.\n\ntang是一个咸鱼供应商,他告诉zhu在他那里面有$N$条咸鱼(标号从1到N)可以被用来制作.\n\n每条咸鱼都有一个咸鱼值$K_{i}$,初始时所有$K_i$都是$0$.\n\nzhu是一个特别的人,他有$M$个咸数(咸鱼数字), 对于每个咸数$x$,他都会让所有满足标号是$x$倍数的咸鱼的咸鱼值异或上$1$.\n\nzhu现在想知道经过了这$M$个咸数的筛选之后,最终有多少条的咸鱼的咸鱼值是$1$?"}},{"title":"Input","value":{"format":"MD","content":"输入的第一行包含一个整数$T$,表示有$T$组数据.\n\n对于每组数据:\n\n输入第一行只有两个整数$N$,$M$.\n\n接下来一行有$M$个整数,依次对应zhu的每个咸数 $a_i$.\n\n数据保证:\n\n* $1 \\leq T \\leq 1000$\n\n* $1 \\leq N \\leq 10^9$\n\n* $1 \\leq M \\leq 15$\n\n* $1 \\leq a_i \\leq 2 \\ast 10^5$"}},{"title":"Output","value":{"format":"MD","content":"对于每组数据,输出一行表示答案"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n10 2\n5 8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n10 1\n3\n10 1\n1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Prepared by xiper"}}]}