KHÔI có \(n\) viên kẹo khác nhau.

KHÔI muốn cho LONG ít nhất một viên kẹo.

Hỏi có bao nhiêu cách để KHÔI cho LONG kẹo.

Input

• Số nguyên dương \(t (t \leq 1000)\) - số test.
• Mỗi test chứa \(1\) số nguyên dương \(n(n \leq 10^4)\)

Output

• Số cách cho kẹo % \(10^5\).

Example

2
1
2 

1
3