Description

在一张N∗N的棋盘上，放置N个車，使得所有車都无法互相直接攻击得到，（車可以直接攻击到其所在的横行，竖列），现在输入一个整数N，表示在N∗N的棋盘上放N个車，请输出使得所有車都无法互相直接攻击得到的方案数的答案位数。 例如下面这样的摆法，是4車的一个解 （1代表有車，0代表没有）

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0

Input Format

一个整数T(T<10) 每行一个整数N(1<N<5000)

Output Format

输出使得所有車都无法互相直接攻击得到的方案数的答案位数

1
2​

1​

Hint

2*2的棋盘大小可以有两种方法

1 0

0 1

和

0 1

1 0

所以说方法数为2，2的位数是1位输出1