Description

zsf要到上海去看世博会。从小和山出发去火车东站要乘坐好多公交车，而且zsf在路上还要吃好多好东西。

现在zsf身上有n元钱，他把钱换成10元，5元，1元面值的，其中10元和5元的至少有一张，1元至少有4个(张)，好方便坐公交、买好吃的。

换的方法肯定有很多种，你能算出到底有多少种换法吗?

Input

第一行输入一个正整数t(1≤t≤200)，表示共有t组数据。每组数据有一个正整数n(19<=n<=1000)

Output

对应每组数据输出换法数

Sample

Input

3
19
50
123

Output

1
16
121

Source: KIX