当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
老谈在寻找黑珍珠的路上，遇到了一些麻烦，他需要回答对守关人的问题才能继续前往，他找到了聪明的你，想要你来帮他解决这个问题。
已知K！=1*2*3*……*（K-1）*K
令S=1*1！+2*2！+……+（n-1）*（n-1）！
求S mod n的值
第一行输入一个整数T（<=1000）代表一共有多少个测试数据
以下T行，每一行都是一个测试数据。
每个测试数据只包括一个整数N。（我们保证2<=n<=10^8）
一个测试数据输出一行，每行包括一个整数代表S MOD N的值。
1 3
2
S=1*1！+2*2！=5且5 mod 3=2
| 时间上限 | 内存上限 |
| 1000 MS | 128 MB |